Projects per year
Abstract
We present a new, simple compact proof of the known strong duality theorem of tropical linear programming with one-sided constraints. This result together with properties of subeigenvectors enables us to directly solve a special tropical linear program with two-sided constraints. We also study the duality gap in tropical integer linear programming. A direct solution is available for the primal problem. An algorithm of quadratic complexity is presented for the dual problem. A direct solution is available provided that all coefficients of the objective function are integer. This solution provides a good estimate of the optimal objective function value in the general case.
Original language | English |
---|---|
Pages (from-to) | 1011-1026 |
Number of pages | 16 |
Journal | Journal of Optimization Theory and Applications |
Volume | 180 |
Issue number | 3 |
Early online date | 2 Nov 2018 |
DOIs | |
Publication status | Published - Mar 2019 |
Keywords
- Tropical linear programming
- Tropical integer programming
- Duality
- Residuation
Fingerprint
Dive into the research topics of 'A note on tropical linear and integer programs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Perron-Frobenius Theory and Max-Algebraic Combinatorics of Nonnegative Matrices
Butkovic, P.
Engineering & Physical Science Research Council
12/03/12 → 11/03/14
Project: Research Councils