EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3894. Algorithm for Solving Combinatorial Optimization Problems with Fractional-Linear Objective Functions

Invited abstract in session TC-52: Exact methods in combinatorial optimization (Contributed), stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Liudmyla Koliechkina
Department of Algorithms and Databases, Faculty of Mathematics and Computer Science, University of Lodz

Abstract

This annotation proposes an algorithm for solving combinatorial optimization problems with fractional-linear objective functions. Such problems are ubiquitous in diverse domains including operations research, scheduling, and network optimization, where the goal is to find an optimal arrangement of elements from a finite set.
The proposed algorithm uses the properties of combinatorial configurations of permutations and their graphs.
The essence of the algorithm is to perform the following steps:
the coefficients of the numerator and denominator of the fractional linear function are determined, the elements of the permutation are specified;
for a selected pair of adjacent permutations, the difference in the values of the linear fractional function is calculated;
based on the calculated coefficients and signs of the differences, a structured permutation graph is formed, which allows you to analyze changes in the values of the objective function at the vertices of the graph;
for the selected elements of the permutation in the graph, a Hamiltonian path is formed along which the values of the objective function change;
extreme values of the objective function are calculated, which are achieved at the extreme points of the permutation graph.

This algorithm allows you to solve combinatorial optimization problems with fractional linear objective functions by analyzing the function values for various permutations and constructing a structured permutation graph.

Keywords

Status: accepted

Back to the list of papers