Duality for mixed-integer convex minimization (Q304264)

This paper studies duality in a combinatorial optimization problem with convex objective, convex constraints and the requirement that some of the variables are integer. In particular, this work extends the standard Karush-Kuhn-Tucker conditions so that it involves mixed integer-free polyhedra instead of separating hyperplanes. The authors begin with an overview of duality and previous attempts to extend the standard conditions followed by a presentation of mixed integer optimality certificates which are used for the proposed extension. The last sections of the article present the case of mixed integer convex dual programs and a technical appendix containing the details of some of the proofs of the presented theorems.