ILP and MILP

[Thomas]

Hello,

I am currently using Gurobi to solve a number of scheduling problems. We are
simply testing for schedulability and are not looking to optimise anything at
this time.

We have two formulations, an ILP model and a Mixed ILP model. In the ILP model Binary
variables are used to represent the location each job is assigned in the given schedule.
In the MILP model some of these binary variables are replaced with continuous variables,
this allows us to model the splitting of jobs.

We observe that over a large number of examples, if our jobs are schedulable (the model is feasible) under ILP
they are identically solved as an MILP model. It seems that jobs/variables are not
split (given non integer values) unless required. What causes this behavior?

Thanks,
Tom

[Kostja Siefen]

Hello Thomas,

if the objective value of your ILP/MILP is zero (i.e. you are only searching for a feasible solution) Gurobi will stop after the first feasible solution has been found. 

There are multiple ways how feasible solutions can be found but it's absolutely common that continuous variables have integer values, for example if the variable bounds are integer.

Kostja

[Thomas]

Hello Kostja,

Thanks for the response!

Would you be able to give some specifics as to why its common to see this behaviour? It would be very useful to understand what Gurobi is doing. I'm a PhD student so I need something to reference.

Thanks again,
Tom

[Diman Tootaghaj]

Hi Tom,
I'm also using gurobi for academic purposes and I have the same question.
I feel gurobi is using a primal-dual approximation algorithm to find an approximate solution of ILP.

http://www.cs.toronto.edu/~bor/2420f10/williamson-primal-dual.pdf

Please correct me if I'm wrong.

Bests,

[Tobias Achterberg]

Tom and Diman,

no, Gurobi is not using a primal-dual approximation algorithm. In order to solve
MILPs (or ILPs) we use an LP-based branch-and-cut algorithm.

The fact that in MILPs many continuous variables will have a solution value that
is equal to one of their bounds (often zero for many applications) is directly
related to the simplex algorithm that we use to solve the LP relaxations. The
simplex algorithm (as opposed to an interior point algorithm) always finds a
vertex solution as optimal solution to an LP relaxation (if there is one). This
means, that the number of variables that can be away from their bounds is
limited by the number of constraints in the model (because the basis has size m
x m, with m being the number of constraints, and only basic variables can be
away from their bounds). Moreover, it is very typical that the simplex algorithm
selects an optimal vertex where many slack variables are basic, which means that
much less than m structural variables will be basic. Hence, in most cases a
significant fraction of the variables will be non-basic, which means that they
are either equal to their lower or their upper bound.


Best regards,

Tobias

[Diman Tootaghaj]

Thanks a lot Tobias,
That makes things much more clear now.
Suppose I have an MIP problem, where the variables are either 0 or 1.
What if I fix the MIPGap to be N. Does it mean that gurobi will find a solution with at most N wrong variables from the optimal solution?
Is there any reference for branch and cut algorithm which proves the bounds from optimal solution when we fix the MIPGap to N?
 
Thanks,
Diman

[Tobias Achterberg]

The MIPGap parameter is just an abort criterion for the branch-and-cut
algorithm. Namely, (assuming minimization) if we have found found a feasible
solution of value c' and have proven that the optimal objective value is at
least c", then Gurobi aborts as soon as s' - s" <= MIPGapAbs or (s'-s")/|s'| <=
MIPGap.

If your objective function is to minimize the sum of all binary variables, and
you set the MIPGapAbs to N, then the solution provided by Gurobi will be at most
N away from the objective value of an optimal solution. But it could very well
be that none of the variables has a value in the Gurobi solution that is
identical to a value in an optimal solution. It only means that the objective
function value is at most N away from the optimal objective function value.

Regarding a good reference, I suggest to look at the book "Integer Programming"
by Laurence Wolsey.

Regards,

Tobias