MATLAB Answers

Finding feasible solution with intlinprog

11 views (last 30 days)
Steffen on 8 Jul 2020
Edited: Steffen on 10 Jul 2020 at 6:34
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?


Sign in to comment.

Answers (1)

Alan Weiss
Alan Weiss on 9 Jul 2020
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

  1 Comment

Steffen on 10 Jul 2020 at 6:33
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');
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?

Sign in to comment.

Translated by