Where do the extra variables come from in integer/binary optimization?

If I use the following code

cvx_solver gurobi 
    variable x(1000) integer;
    x <= 10*rand(1000,1);
    maximize sum(x); 

Gurobi reports 2000 variables, 1000 equality constraints, 2000 nonzero coefficients. Presumably the extra variables appear as a consequence of the model building process. The Gurobi presolver makes quick work of them, but is there anything one can do to avoid creating extra variables in the first place?


No, there is no way to avoid creating them. That’s simply part of the process of turning problems into solvable form. In this particular case, the extra variables are probably nonnegative slack variables added to convert the inequalities into equations.

Like you said, Gurobi makes quick work of them, and that’s good. CVX depends on that behavior. In fact, CVX often creates many more additional variables that Gurobi never sees, because it makes “quick work” of them in its own presolve stage.