Total Unimodularity in Integer QP

Question

I have a Quadratic Programming problem with linear constraints. My objective is Quadratic-Convex, the constraint matrix is Totally Unimodular (similar to assignment or network flow problems), and the variables are Binary. I know that if an LP has Totally Unimodular constraint matrix $A$ and integral $b$ matrices, then the Optima will be integral.

Now, while solving my QP with a nonlinear solver (MINOS 5.51) with relaxed variable (ignoring the integrality), I get almost all the solutions as integral. Most of the time, I get all variables as integral. Only 2 in 20,000 variables or 2 in 84 thousands variables are non-integral.

My question is, is there any theory which talks about the implication of Total Unimodularity in QP or MIQP or convex optimization? Is there any explanation why my problem is getting an integral solution? Are there any articles or books which discuss this issue?

Answer 1

Let me assume that the feasible region is full dimensional. There are two issues:

1. None of the corner points of the feasible region might be optimal (since the objective function is not linear).

2. A QP is typically solved with a different algorithm (interior point vs [simplex method or interior point followed by the simplex method]). Therefore, if an entire face of the feasible region is optimal (which is possible when the objective function is not strictly convex), the optimization algorithm will find a non-corner point solution.

Answer 2

What you're looking for is most likely an extension of the fundamental theorem of linear programming.

Such extensions give generalized sufficient conditions to when $\min_{x\in P} f(x)$, where $P$ is a polyhedron, has a global minimizer in one of its vertices.

For example, the fundamental theorem of linear programming also holds when $f(x)$ is a concave function.

This paper gives several possible extensions of the fundamental theorem of linear programming for when $f$ is concave, quasi-concave or differentiable and strictly quasi-convex.