Subadditive approaches in integer programming

Diego Klabjan

Abstract

Linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory has been developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We present computational experiments, which show that the new algorithm is tractable.
BibTeX
@article{klabjan2007subadditive,
  author = {Diego Klabjan},
  title = {{Subadditive approaches in integer programming}},
  journal = {Eur. J. Oper. Res.},
  year = {2007},
  url = {https://openreview.net/forum?id=5rZr7AxdKgy},
}

Loading related content...

Figure