A note on tropical linear and integer programs

Peter Butkovic

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
153 Downloads (Pure)

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 languageEnglish
Pages (from-to)1011-1026
Number of pages16
JournalJournal of Optimization Theory and Applications
Volume180
Issue number3
Early online date2 Nov 2018
DOIs
Publication statusPublished - 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.

Cite this