Gurobi Java force variable to be nonzero

[jannis...@materna.de]

I am currently trying to force a variable to be nonzero, but I can only find a way to force a Variable to be greater, or equal than something.

This is what i currently use, ut come on, there must be a better way to do this:

for(int i = 0; i < X.length; i++)
{
     GRBLinExpr placeholder = new GRBLinExpr();
     placeholder.addTerm(1.0, X[i]);
     model.addConstr(placeholder, GRB.GREATER_EQUAL, 0.000000001, "nonzero" );
}

[Tobias Achterberg]

This is actually a highly fundamental property of linear and mixed integer programming,
that you can *not* deal with strict inequalities on continuous variables.

From a theoretic point of view, strict inequalities lead to open sets and thus, the
minimum for some objective function would not necessarily be part of the feasible region
(and hence undefined). Consider the following simple problem:

min x
s.t. x > 0

This problem does not have a solution, since the minimum is undefined. The infimum is 0,
but 0 is not feasible. For any feasible solution x = eps > 0, there is another feasible
solution with better objective value, for example x' = eps/2.

From an algorithmic point of view, the linear programs are solved with the simplex
algorithm. This algorithm works on combinatorial structures, namely bases of the
constraint matrix. A basis is a subset of the set of variables, such that the
corresponding sub-matrix of A is a non-singular square matrix. The non-basic variables
(i.e., the variables that are not part of the basis) define the inequalities or bound
constraints that are satisfied by equality for the basic solution. For this reason, the
simplex algorithm can only enforce equality. For the basic variables (and slack variables)
it just checks feasibility (by calculating the basic solution as the unique solution of
the resulting square linear system). Hence, there is no way for the simplex algorithm to
enforce strict inequality.

From a practical point of view, strict inequality does not make any sense, because the
algorithms work with floating point numerics. Hence, values x and x+eps cannot be
distinguished if eps is small enough. Because of this, any feasibility and optimality
check in the algorithm needs to be performed with respect to tolerances. Thus, tiny
violations of the constraints are considered to be okay and the solution is accepted to be
feasible. As a result, if you would require strict inequality like

x > 0

and model this as something like

x >= 1e-100

then the solution x = 0 would still be accepted as feasible, because the tiny violation is
clearly below the feasibility tolerance (which is 1e-6 in default settings).


If you really want to have strict positivity in your model, then you need to think very
carefully about which value you consider to be reasonably far away from zero to be
relevant for your application. Then, use this value as right hand side in your
larger-or-equal inequality. Your example of using

x >= 0.000000001

is clearly not a good choice, because your 1e-9 is smaller than the default feasibility
tolerance of 1e-6 and thus, x = 0 might be considered to be feasible.


Best regards,

Tobias