Optimization problem under two-sided (max, +)/(min, +) inequality constraints
Applications of Mathematics, Tome 65 (2020) no. 6, pp. 777-783
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library
$(\max ,+)$-linear functions are functions which can be expressed as the maximum of a finite number of linear functions of one variable having the form $f(x_1, \dots , x_h) = \max _j(a_j+ x_j)$, where $a_j$, $j = 1, \dots , h$, are real numbers. Similarly $(\min ,+)$-linear functions are defined. We will consider optimization problems in which the set of feasible solutions is the solution set of a finite inequality system, where the inequalities have $(\max ,+)$-linear functions of variables $x$ on one side and $(\min ,+)$-linear functions of variables $y$ on the other side. Such systems can be applied e.g. to operations research problems in which we need to coordinate or synchronize release and completion times of operations or departure and arrival times of passengers. A motivation example is presented and the proposed solution method is demonstrated on a small numerical example.
$(\max ,+)$-linear functions are functions which can be expressed as the maximum of a finite number of linear functions of one variable having the form $f(x_1, \dots , x_h) = \max _j(a_j+ x_j)$, where $a_j$, $j = 1, \dots , h$, are real numbers. Similarly $(\min ,+)$-linear functions are defined. We will consider optimization problems in which the set of feasible solutions is the solution set of a finite inequality system, where the inequalities have $(\max ,+)$-linear functions of variables $x$ on one side and $(\min ,+)$-linear functions of variables $y$ on the other side. Such systems can be applied e.g. to operations research problems in which we need to coordinate or synchronize release and completion times of operations or departure and arrival times of passengers. A motivation example is presented and the proposed solution method is demonstrated on a small numerical example.
DOI :
10.21136/AM.2020.0001-20
Classification :
90C26, 90C30
Keywords: nonconvex optimization; $(\max, +)/(\min, +)$-linear functions; OR - arrival-departure coordination
Keywords: nonconvex optimization; $(\max, +)/(\min, +)$-linear functions; OR - arrival-departure coordination
@article{10_21136_AM_2020_0001_20,
author = {Zimmermann, Karel},
title = {Optimization problem under two-sided (max, +)/(min, +) inequality constraints},
journal = {Applications of Mathematics},
pages = {777--783},
year = {2020},
volume = {65},
number = {6},
doi = {10.21136/AM.2020.0001-20},
mrnumber = {4191368},
zbl = {07285956},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.21136/AM.2020.0001-20/}
}
TY - JOUR AU - Zimmermann, Karel TI - Optimization problem under two-sided (max, +)/(min, +) inequality constraints JO - Applications of Mathematics PY - 2020 SP - 777 EP - 783 VL - 65 IS - 6 UR - http://geodesic.mathdoc.fr/articles/10.21136/AM.2020.0001-20/ DO - 10.21136/AM.2020.0001-20 LA - en ID - 10_21136_AM_2020_0001_20 ER -
%0 Journal Article %A Zimmermann, Karel %T Optimization problem under two-sided (max, +)/(min, +) inequality constraints %J Applications of Mathematics %D 2020 %P 777-783 %V 65 %N 6 %U http://geodesic.mathdoc.fr/articles/10.21136/AM.2020.0001-20/ %R 10.21136/AM.2020.0001-20 %G en %F 10_21136_AM_2020_0001_20
Zimmermann, Karel. Optimization problem under two-sided (max, +)/(min, +) inequality constraints. Applications of Mathematics, Tome 65 (2020) no. 6, pp. 777-783. doi: 10.21136/AM.2020.0001-20
Cité par Sources :