Forcing Gurobi to start Branch and Bound

[Eran Schweitzer]

Hello everyone,

I'm solving a large placement problem with gurobi 7.0 using the python interface.
The problem essentially solves for two large permutation matrices (there are a few other continuous variables but the binaries form the lions share).
To solve the problem, I am using an ADMM approach: I split it into zones, and solve the zones separately.
There are a handful of variables that are present in two different zones.
I iterate over the problems, each time updating the objective (and objective only!) to try and force convergence on these boundary variables.

In the objective update I introduce quadratic terms, basically sum( (x_i - mean(x_i))**2 ) where x_i are the boundary terms mentioned above,
and mean(x_i) is a parameter calculated at the end of each iteration, which is the average of each boundary variable over it's iterations
( so if x_i shows up in two zones it will be mean(x_i) = (x_i,zone1 + x_i,zone2)/2).

The first iteration obtains a feasible solution for each of the zones.
However, in subsequent iterations, some of the larger zones (roughly 2*(300^2) binary variables) take over an hour just on the root simplex.
I realize this is a very large problem, but note that I already have a feasible solution for the model from the first iteration.

For my particular application, I am not actually that interested in the optimum.
I would like the boundary variables to converge, but beyond that I mainly care about feasibility. The objective is there to mainly push the solution in a particular direction.
For that reason, I would like to forcefully employ time limits to stop the optimization given there is a feasible solution.
However, I am running into a situation where some of these larger zones are returning 0 solutions, at which point when I query the variables everything breaks.

my questions are:
1) How can a model that has a feasible solution, where only the objective was changed suddenly have no feasible solution?
2) Since I am only interested in improving the incumbent and not so much in optimality, is there a way to tell Gurobi to quit working on finding a lower bound in the root simplex and simply start branching? The MIP gap is basically immaterial.

Many thanks,
Eran

[Daniel Espinoza]

Hi Eran,

I would suggest using an absolute value penalty instead of quadratic, as that should make solving each node faster.

Also, have you tried to `grow` the solution from one piece to the next? i.e. to give it as a boundary condition and then only add penalties for the places where you could not grow the solution?

If you don't care about objective value, the you could set the parameter `SolutionLimit` to one, that will make Gurobi to stop as soon as it finds a feasible solution

Hope it helps,

Daniel

[Eran Schweitzer]

Thanks Daniel,

I will try the absolute value modification and see how that works.
I'm not entirely sure I understand what you mean by 'growing' the solution.
If what you mean is to solve the first subproblem and then solve the second subproblem where I apply a penalty if it deviates from subproblem 1's solution in the shared variables than this is not a possible approach since I don't have any natural ordering for the subproblems.
That is, there is no good reason to give problem 1 precedence over problem 2.

I did experiement with setting the 'SolutionLimit' to a low number, the problem is that while I am primarily interested in feasibility, particularly for the smaller subproblems I prefer to be closer to my defined optimum.
Additionally, the problem is not so much in finding a solution but in getting past the root relaxation. As I mentioned I already have one feasible solution.

Thank you for the suggestions,
Eran