Advice on adding symmetry breaking constraints to MIP models

[Eirik Fernandez Cuesta]

Hi all,

I have a MIP model with columns representing routes for helicopters where I want to minimize the cost.
In this model I want to test symmetry breaking constraints. The constraints work in the way that they require helicopter n to be used at least as much as vehicle n+1 if n and n+1 are identical helicopters.
I know that Gurobi has ways of avoiding symmetry, but I would like to test if mine can do a better job.

Now, the results with my symmetry breaking constraints are roughly the same as without; it's hard to argue either way.
However, I notice that the quality of the root relaxation is worse when I have the symmetry ctrs included. This is in theory illogical as these should not reduce the solution space in the root node.
The reason for this I believe is due to the pre-solve performing differently when the symmetry constraints are added. This is confirmed by turning pre-solve off, as the value of the root relaxation then becomes the same.

Now, an approach I would like to test is to try to add the symmetry breaking constraints after the pre-solve stage to get a better lower bound in the route node.

I was thinking something along the lines of this:

_model.getEnv().set(GRB.IntParam.PreCrush,1);
_model = _model.presolve();
 AddSymmetry();

_model.update();
_model.optimize();

but test with this shows that something is not working as the optimal solution (found earlier) is now not longer feasible.

Any suggestions to the best way to go forth?

I'm also considering using callback to add the cuts later, but it seems silly since I want to all symmetry constraints in the beginning anyway.


Regards

Eirik Fernandez Cuesta

[Sonja Mars]

Hi Erik,

> _model.getEnv().set(GRB.IntParam.PreCrush,1);
> _model = _model.presolve();
> AddSymmetry();
>
> _model.update();
> _model.optimize();
>
> but test with this shows that something is not working as the optimal solution (found earlier) is now not longer feasible.

How did you find out, it is not feasible any more? And what do you mean by “found earlier”? If you are using symmetry breaking constraints maybe they cutoff your solution.

Additionally you can try to take a look at the LP-files of your model (for a very small example) before presolve, after presolve and after adding the symmetry breaking constraints. Therefore just insert the lines.

_model.update()
_model.write(“myfile.lp”)

Maybe you can find something in these files that causes the infeasibility.

Best regards,
Sonja

-----------------------------------------------------------------
Dr. Sonja Mars
Gurobi Optimization

[Eirik Fernandez Cuesta]

Hi and thank you for your reply,

I know that the previously optimal solution was cut off by the symmetry breaking constraints because the objective value was not as good as in the run were the symmetry breaking constraints were added from the start in the original model.
The reason that I wanted to try adding symmetry later was because the lower bound to the problem in the root node was worse when I had them included. I don't know why this is other than it has to do with presolve working better when the symmetry constraints are omitted.
I managed to obtain what I wanted by adding the symmetry breaking constraints by using callback in the root node.

Best regards
eirik

[Jakob Sch.]

Hi Eirik,

So to sum things up:

Model with symmetry breaking constraints added: worse root relaxation, but better feasible solution (incumbent)
Model without symmetry breaking constraints: better root relaxation, but worse feasible solution
Is that correct? Can you give some statistics on the models? Size of the LP, Lower bounds. It would help if you could provide examples (MPS or LP files).

Best regards,
Jakob