A Strong Dual for Conic Mixed-Integer Programs

Diego A. Morán R., Santanu S. Dey, Juan Pablo VielmaSIAM J. Optim 2012 · DOI

TL;DR

This paper extends the theory of duality for mixed-integer linear programming to the more general setting of mixed-integer conic programming. The authors introduce a subadditive dual for these problems and, under a specific condition on the primal problem, prove that strong duality holds, meaning the optimal values of the primal and dual problems are equal when they are finite.

What Problem Does This Paper Address?

Optimization theory often seeks to find bounds on the optimal objective function value of a problem. Duality theory provides a powerful way to achieve this by constructing a related "dual" problem whose optimal value provides a bound for the original "primal" problem. For linear programming (LP) and conic programming, duality is well-understood. Mixed-integer linear programming (MILP) also has a well-established subadditive dual. However, extending this duality theory to mixed-integer conic programming (MICP) – a generalization that includes conic programming problems with integer variables – presents a significant challenge. This paper aims to bridge this gap by constructing and analyzing a subadditive dual for MICP and establishing conditions under which strong duality holds.

Methods

The core of this paper is the construction of a subadditive dual for mixed-integer conic programs. This involves generalizing the concepts of subadditivity and nondecreasing functions with respect to a cone, which are fundamental to the subadditive dual of MILP. The authors then build upon existing results in conic programming duality and properties of value functions to prove their main theorem. Key steps include:

  • Defining the Subadditive Dual: The paper formally defines the dual problem (D) for a given primal MICP (P), leveraging the concept of subadditive and K-nondecreasing functions.
  • Weak Duality: They first establish weak duality, showing that any feasible solution to the dual provides a valid bound for the primal.
  • Finiteness Equivalence: A crucial part of proving strong duality is showing that the primal problem is finite (i.e., has a finite optimal value) if and only if its continuous relaxation is finite. This requires a specific technical condition on the primal problem.
  • Constructing a Feasible Dual Solution: For the case where strong duality holds, the authors construct a specific feasible solution for the dual problem that achieves the primal's optimal value. This construction involves analyzing the value function of the primal problem and carefully defining a new function that satisfies the dual's constraints.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Generalizing Duality: The paper successfully extends the well-established subadditive duality framework from MILP to the more general class of MICP. This opens up new avenues for theoretical analysis and algorithmic development in this area.
  • The Importance of a Technical Condition: The authors identify a critical condition – the existence of a strictly feasible primal solution (i.e., $Ax >_K b$) – that is essential for establishing strong duality. This condition plays a role analogous to rationality of data in MILP duality proofs.
  • Value Function Properties: The analysis of the primal problem's value function is key. Understanding its subadditivity and nondecreasing properties allows for the construction of a feasible dual solution that achieves strong duality.
  • Bridging Continuous and Discrete: A significant insight is the demonstration that under the stated condition, the finiteness of the mixed-integer problem is equivalent to the finiteness of its continuous relaxation. This is a non-trivial result for conic programs.

Key Results

The paper's main contribution is Theorem 2.4 (Strong duality), which states that if there exists a primal feasible solution $x \in \mathbb{Z}^{n_1} \times \mathbb{R}^{n_2}$ such that $Ax >_K b$, then:

  1. The primal problem (P) is finite if and only if the dual problem (D) is finite.
  2. If (P) is finite, then there exists a function $g^*$ feasible for (D) such that $g^*(b) = z^*$ (the optimal value of the primal), implying $z^* = p^*$ (the optimal value of the dual).

The paper also establishes weak duality and provides preliminary results concerning the finiteness of conic mixed-integer problems and their continuous relaxations.

Limitations and Future Work

  • Sufficiency of the Condition: While the paper establishes a sufficient condition for strong duality, it does not claim it is necessary. Future work could explore whether this condition can be relaxed.
  • Algorithmic Implications: The theoretical results lay the groundwork for developing new algorithms for solving MICPs. Investigating how these dual formulations can be used in practice, perhaps in conjunction with cutting-plane methods, would be a natural next step.
  • Specific Cones: The paper deals with general conic programming. Exploring the implications of strong duality for specific types of cones (e.g., second-order cone, exponential cone) could yield more specialized insights.
  • Computational Complexity: The paper focuses on theoretical duality. Analyzing the computational complexity of finding the dual solution and its relationship to the primal problem's complexity would be valuable.

Summary updated

BibTeX
@article{r2012strong,
  author = {Diego A. Morán R. and Santanu S. Dey and Juan Pablo Vielma},
  title = {{A Strong Dual for Conic Mixed-Integer Programs}},
  journal = {SIAM J. Optim},
  year = {2012},
  doi = {10.1137/110840868},
}

Loading related content...

Figure