Mixed-integer support in CVX 2.0

Gurobi and MOSEK, the first commercial solvers we have connected to CVX, support mixed-integer models: models with one or more variables constrained to assume integer or even binary (0/1) values. Such variables can be used not just in linear programs, but nonlinear convex programs as well.

We have decided to introduce the ability to specify integer and binary variables into CVX models as well. To use this feature, simply add the integer or binary keyword to the relevant variable declaration; for example:

variable x(10) integer;
variable y(3,3) binary;

Models with integer and binary variables must still obey all of the same disciplined convex programming rules that CVX enforces for continuous models. For this reason, we are calling these models mixed-integer disciplined convex programs, or MIDCPs.

Danger! Danger!

Mixed-integer DCPs are not convex.

As with mixed-integer linear and quadratic programs (MILPs/MIQPs), MIDCPs are theoretically intractable. In practice, your results will vary. Solving them requires the combination of a continuous optimization algorithm, such as an interior-point method, and an exhaustive search, such as a branch-and-bound. In some cases, your model will be solved globally after only a few branches. In other cases, the solver will fail to find a global solution in any reasonable amount of time.

Furthermore, solvers for MIDCPs are less mature than those devoted specifically to MILPs/MIQPs. Most of the developments that have improved the performance of MILP solvers map logically to MIDCPs, but MIDCPs present new challenges. We hypothesize that solver performance will be more sensitive to problem size with MIDCPs than with MILPs, and that the best results will come with models that make only sparing use of integer variables.

Non-convex constraints as MIDCP constraints

One of the more interesting consequences of MIDCP support is that, in limited cases, a nonconvex model can be transformed in to an MIDCP. For instance, suppose x is a vector variable, and l and u are constant vectors. If you were to specify the constraint

l <= abs(x) <= u;

in CVX, you would get the dreaded Disciplined convex programming error: message. But in fact, this constraint can be represented as an MIDCP by introducing a vector of binary variables:

varaible xb(size(x)) binary;
l - xb .* ( l + u ) <= x <= u - xb .* ( l + u );

For a nonlinear example, consider these constraints:

max(norm(x),norm(y)) <= 2;
min(norm(x),norm(y)) <= 1;

The first constraint is convex, the second is not. But together they can be specified in an MIDCP:

binary variable nb;
norm(x) <= 1 + nb;
norm(y) <= 2 - nb;

We emphasize that the ability to convert nonconvex constraints to MIDCP form is the exception rather than the rule. For instance, the constraint

1 <= norm(x) <= 2;

looks very similar to our first example, but it cannot be converted to an MIDCP. Furthermore, CVX will not perform these conversions for you; you will have to identify and perform them yourself. Do not ignore convexity during the modeling process, assuming that you will be able to convert your model to an MIDCP after the fact!

Solver support

Neither of CVX’s free solvers supports MIDCPs. Gurobi and MOSEK are currently the only choices for these problem types. Academic users will be able to use either solver (or both!) at no charge. Commercial users can use them by purchasing a CVX Professional License.

We hope to add support for a free mixed-integer solver in a future version of CVX. We are currently studying the use of GLPK, the GNU Linear Programming Kit. Of course, as the name implies, GLPK will only support models that can be converted to LPs or MILPs. If a reliable, free solver that supports both integer variables and conic constraints becomes available, we will certainly consider it; please contact us!

Can a mixed-integer problem truly be disciplined?

Among those of you who know us well, there might be some surprise at our decision to include mixed-integer support. After all, we have been, and remain, very strong advocates for a deliberate approach to convex programming. Indeed, we coined the term disciplined convex programming to describe our philosophy: that the best way to exploit convexity is not to search for it after the model is constructed, but rather to make convexity an explicit goal of the modeling process itself.

We hold that a proper use of MIDCPs still requires a disciplined approach to model building. As we said above, non-convex models representable as MIDCPs will be the exception, not the rule; it is still necessary to build models with convexity as a goal, not an artifact. The performance limits of MIDCP solvers will tend to limit the use of integer and binary variables in CVX models.

There is no doubt that the addition of MIDCPs to CVX is an experiment for us. It will also be an experiment for our users and our solver partners as well. We look forward to seeing the new applications that arise when modelers can add modest numbers of integer constraints to their models. And we look forward to seeing the algorithms for mixed-integer convex programming improve as a suite of “difficult” test problems accumulates.