Gurobi ignores some constraints in model

[nicola...@liu.se]

Hi,

Using Gurobi to solve some mixed integer problem, but I noticed that in some cases, Gurobi claims to have found an optimal solution, yet the solution it finds violates some constraints. Using Gurobi 6.0.0 and an old ILOG AMPL copy (10.100), here is my situation:

Here are variables and their corresponding constraints

param M = 0.9;
var core_time{pp in P} = sum{t in T, g in G, f in F, ppp in P} x[g, t, f, ppp] * member[g, pp] * Tau[t] / (ppp * e[t, ppp] * f);
subject to meet_deadline{pp in P}: core_time[pp] <= M;

The output I get shows an invalid solution:

Gurobi 6.0.0: timelim 300
Gurobi 6.0.0: optimal solution; objective 3.428571429
5167 simplex iterations
685 branch-and-cut nodes
No dual variables returned.

[ .... ]

core_time [*] :=
1 2         2 0         3 1.42857   4 1.42857
;

If I use Gurobi 6.5.0, It gets even worse:

Gurobi 6.5.0: timelim 300
Gurobi 6.5.0: infeasible

I can add 3 additional constraints to force a particular solution:

subject to task_1_on_2_cores_at_freq_2: sum{g in G} x[g, 1, 2, 2] = 1;
subject to task_2_on_1_core_at_freq_2: sum{g in G} x[g, 2, 2, 1] = 1;
subject to task_3_on_1_core_at_freq_2: sum{g in G} x[g, 3, 2, 1] = 1;

And Gurobi 6.0.0 finds a solution that is just fine, and that I checked to be valid with my problem; I didn't dare to check (again) all constraints in my model I wrote, but of course I assume they are not violated:

Gurobi 6.0.0: timelim 300
Gurobi 6.0.0: optimal solution; objective 13.71428571
5958 simplex iterations
879 branch-and-cut nodes
No dual variables returned.

[ .... ]

core_time [*] :=
1 0.5        2 0.714286   3 0.714286   4 0.5
;

Whereas Gurobi 6.5.0 still fails to compute a valid solution:

Gurobi 6.5.0: timelim 300
Gurobi 6.5.0: infeasible

Without the 3 constraints, CPLEX 12.6.1.0 succeeds in finding a correct solution, although it is a pretty bad one

CPLEX 12.6.1.0: timelimit=300
CPLEX solution status 107 with fixed integers:
    time limit with integer solution
CPLEX 12.6.1.0: time limit with integer solution; objective 52
255463 MIP simplex iterations
166786 branch-and-bound nodes

[ .... ]

core_time [*] :=
1 0      2 0.5    3 0.5    4 0.25
;

And with the three additional constraints above, CPLEX 12.6.1.0 still finds a valid solution

CPLEX 12.6.1.0: timelimit=300
CPLEX solution status 101 with fixed integers:
    optimal integer solution
CPLEX 12.6.1.0: optimal integer solution; objective 13.71428571
78 MIP simplex iterations
0 branch-and-bound nodes

[ .... ]

core_time [*] :=
1 0.5        2 0.714286   3 0.5        4 0.714286
;

By the way, I try to use a quadratic equality constraint

subject to number_of_allocated_cores_matches_group_size_1{t in T}: sum{g in G, f in F, pp in P} x[g, t, f, pp] * pp = sum{g in G, f in F, pp in P} x[g, t, f, pp] * size[g];

but since Gurobi (6.0.0 or 6.5.0) or CPLEX doesn't seem to like it

Gurobi 6.0.0: timelim 300
Gurobi 6.0.0: Gurobi cannot handle quadratic equality constraints.

Gurobi 6.5.0: timelim 300
Gurobi 6.5.0: Gurobi cannot handle quadratic equality constraints.

CPLEX 12.6.1.0: timelimit=300
CPLEX 12.6.1.0: Constraint _scon[43] is not convex quadratic since it is an equality constraint.

So I sneak a workaround, that is one copy of the constraint above with a lower of equal constraint and another copy with a higher or equal constraint:

subject to number_of_allocated_cores_matches_group_size_1{t in T}: sum{g in G, f in F, pp in P} x[g, t, f, pp] * pp <= sum{g in G, f in F, pp in P} x[g, t, f, pp] * size[g];
subject to number_of_allocated_cores_matches_group_size_2{t in T}: sum{g in G, f in F, pp in P} x[g, t, f, pp] * pp >= sum{g in G, f in F, pp in P} x[g, t, f, pp] * size[g];

The conjunction of both constraints above should be equivalent to the equality constraint I'm trying to make, but it seems too easy to have solvers to do something they claim they can't do. Am I missing something? Are these two constraints together not the same as the unique one I'm trying to express? In any way, both Gurobi and CPLEX stop complaining but they behave as described above.

I would use CPLEX then, but it fails at finding solutions with other constraints I want to try (claiming it is unfeasible), whereas Gurobi finds a satisfying solution.
Let us forget CPLEX, but does anyone knows what can make Gurobi 6.0.0 to ignore constraints and claims to have found an optimal solution?

Any help would be greatly appreciated.

Best,

Nicolas

[Tobias Achterberg]

Hi Nicolas,

two inequalities with opposite sense are certainly equivalent to a single
equation, at least in terms of the mathematical model. In principle, neither
Gurobi nor CPLEX can solve non-convex quadratically constrained models (more
precisely, with Q matrices that are not positive semi-definite). But sometimes
you can get lucky and they can, and this is where the splitting of the equation
into two inequalities may come into play. Namely, such a modification probably
leads to a difference in the presolving process, where in one case you are lucky
and the solver can fix the resulting system to become psd. This happens for
example when binary variables are included in the product terms, which can then
be linearized. Or, alternatively, one can sometimes add M*(x^2 - x) for binary
variables to the constraint with a big coefficient M in order to increase the
diagonal of the Q matrix, which eventually makes it psd. The trick here is that
for binary variables x^2 = x, which means adding (x^2 - x) is not changing the
model. Unfortunately, applying this trick for very big M values can
significantly impact the numerics of your problem (which may be the reason for
the wrong answers you are observing) and the performance of the solver (because
the relaxation becomes much weaker, since for fractional values of x, x^2 - x is
non-zero).

Thus, my guess is that you are facing numerical issues here that come from the
fact that your model is originally not positive semidefinite. You should try to
find a different formulation for your problem that is psd or, even better,
linear. Of course, I am aware of the fact that this may not be trivial. Modeling
is an art.


Regards,

Tobias

[nicola...@liu.se]

Hi Tobias,

Thank you for your valuable help. I was afraid that I'd need to reformulate my model. It may be an art but it helps a lot to be aware on how it is transformed internally, and this is way beyond my skills.

I turned the quadratic equality constraint into another that involves only binary variables, but Gurobi still refuses it. This may be because I replace an integer vector variable by a binary matrix variable that takes value 1 if the column index of line i matches the i'th value in the vector variable vector, in other words, it boils down to exactly the same. Needless to say, turning it into 2 inequalities still leads to the same unwanted behavior.

I will try to reformulate then. Let me know if that gives you more insight that can provide me more clues.

Best,

Nicolas

[Tobias Achterberg]

If you have quadratic terms on binary variables you can linearize them yourself:

z = x*y <=> {z - x <= 0, z - y <= 0, -z + x + y <= 1}

Of course, this means to introduce one variable and three constraints for each
product of binary variables that appears in your formulation.

[nicola...@liu.se]

I abandonned what I was doing as I couldn't find a way to get rid of the quadratic equality constraint, but I might get back to it and use your trick. Many thanks for your help.

Nicolas