Finding feasible solution with intlinprog

I'm using intlinprog to solve some bigger MILP problems (hundreds or few thousands of variables and constraints).

The solver typically finds solutions after seconds or few minutes. So far so good.

Sometimes I'm interested in just quickly finding a feasible solution for the constraints.

To do this I set the vector for the objective function to the zero vector. When I now start

the optimization it runs and runs and runs (hours...) .... until the timeLimit is reached.

My questions:

a) How can that be? The second optimization is much simpler than the first (the optimal value is

even known: 0) but it does not converge.

b) If this does not work, what could be an alternative way to (quickly) find a feasible solution?

Thanks,

Steffen.

Answer 1

[Alan Weiss]

A nonzero objective function vector can sometimes help intlinprog by breaking symmetry in the constraints. It is never clear with integer linear programming whether specific changes will speed a solution. For more information, see Tuning Integer Linear Programming.

You are free to specify f = [], which probably works the same as specifying an all-zero vector. See f.

Alan Weiss

MATLAB mathematical toolbox documentation

[Steffen Klamt]

Dear Alan,

Thanks for your prompt response.

I tried setting f=[ ] yielding the same strange results (finding a feasible

solution does not converge for a long time while the optimization with full

objective function (which includes the step of finding a feasible solution!)

does it in seconds. I saw this even for different problems. [But at least for a

tiny example a feasible solution could be found this way.]

I now tried another variant via the OutputFcn:

stopfunc = @(x,optimValues,state) ~isempty(x) && ~strcmp(optimValues.phase,'rootlp');

optoptions.OutputFcn=stopfunc;

Together with the given (non-zero) objective function, this seems to work for my examples.

Do you think this makes sense in general? Or is there even a better (more direct) way?

Thanks,

Steffen.