Short Rational Generating Functions For Multiobjective Linear Integer Programming
From MaRDI portal
Publication:6207947
arXiv0712.4295MaRDI QIDQ6207947FDOQ6207947
Publication date: 27 December 2007
Abstract: This paper presents algorithms for solving multiobjective integer programming problems. The algorithm uses Barvinok's rational functions of the polytope that defines the feasible region and provides as output the entire set of nondominated solutions for the problem. Theoretical complexity results on the algorithm are provided in the paper. Specifically, we prove that encoding the entire set of nondominated solutions of the problem is polynomially doable, when the dimension of the decision space is fixed. In addition, we provide polynomial delay algorithms for enumerating this set. An implementation of the algorithm shows that it is useful for solving multiobjective integer linear programs.
This page was built for publication: Short Rational Generating Functions For Multiobjective Linear Integer Programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6207947)
