Finding feasible solution with intlinprog

Question

0 个投票

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Follow Question

Answer 1

Alan Weiss 2020-7-9

2 个投票

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Steffen Klamt 2020-7-10

编辑：Steffen Klamt 2020-7-10

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.

请先登录，再进行评论。

Finding feasible solution with intlinprog

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

回答（1 个）

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

类别

标签

Community Treasure Hunt

Finding feasible solution with intlinprog

0 个评论 显示 -2更早的评论 隐藏 -2更早的评论

回答（1 个）

1 个评论 显示 -1更早的评论 隐藏 -1更早的评论

类别

标签

另请参阅

Community Treasure Hunt

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论