Convex integer program with totally unimodular constraints

Question

Suppose I have a convex (nonlinear) integer program with totally unimodular linear constraints. What are sufficient conditions one can impose on the convex objective function such that relaxing the program to be over the reals will not introduce a integrality gap (i.e. the programs are equivalent)?

Answer 1

I presume you mean the constraints are $Ax \le b$ where the coefficient matrix $A$ is totally unimodular and the entries of $b$ are all integers. Then all extreme points of the feasible region have integer entries. If a linear programming problem with these constraints has an optimal solution, then it has one with all integer entries. The same would be true for minimizing a concave objective over the feasible region. However, if you are minimizing a convex nonlinear objective, it is quite likely that the optimal solution will not be an extreme point, and then there is no reason to expect integer entries.

If you want to impose a condition on the convex objective $f$ (without regard to the constraints), you can do this. Suppose for every unit cell $C_u = \prod_{i=1}^n [u_i, u_i+1] \subset \mathbb R^n$ where $u \in \mathbb Z^n$, the minimum of $f$ over $C_u$ occurs at an extreme point of $C_u$. Then if the problem of minimizing $f$ subject to $Ax \le b$ has an optimal solution, it has one in $\mathbb Z^n$. Namely, such an optimal solution $x^\star$ is in at least one of the cells $C_u$. Adding the constraints $x_i \ge u_i$ and $x_i \le u_{i}+1$ to enforce membership in $C_u$ preserves the property that $A$ is unmodular and $b$ is in integers, so the extreme points of the intersection of the feasible region with $C_u$ are extreme points of $C_u$, and at least one of these has objective value $\le f(x^\star)$.

Conversely, if your $f$ does not have this property, there is a problem with minimizing $f$ as objective and constraints $Ax \le b$ where $A$ is totally unimodular and $b$ is in integers, such that there is no optimal solution in integers. Namely, take some unit cell $C_u$ such that the minimum of $f$ over $C_u$ does not occur at an extreme point of $C_u$, and make the constraints $x_i \ge u_i$ and $x_i \le u_i + 1$, $i=1\ldots n$.

Answer 2

I don't think there is a good answer to your question. For instance f(x) = \sum_i (x_i - 1/2)^2, this function is convex, quadratic, and separable, yet will not end up at an integer solution.

Perhaps the right question is what is the proximity of continuous relaxation to the integer problem?

This is a famous paper by Hochbaum and Shantikumar. https://dl.acm.org/doi/pdf/10.1145/96559.96597

One result they prove is the following THEOREM 1.2. Let the complexity of solving an Integer Linear Programming problem Min $\{\mathbf{c x} \mid A \mathbf{x} \geq \mathbf{b}, \mathbf{0} \geq \mathbf{x} \geq \mathbf{1}, \mathbf{x}$ integer $\}$ be TI $(n, m, A)$, then the complexity of solving a nonlinear separable convex integer optimization problem on $\{\mathbf{x} \mid A \mathbf{x} \geq \mathbf{b}\}$ is $$ \log _2 \frac{B}{2 n \Delta} T\left(8 n^2 \Delta, m, \Delta\right)+T I\left(4 n^2 \Delta, m, A^{4 n \Delta}\right) . $$