The running time complexity of Mixed-integer linear programming (MILP)?

17 ビュー (過去 30 日間)
Frank Dou 2021 年 11 月 25 日

How could we know the running time complexity of Mixed-integer linear programming (MILP)?
Because MATLAB is using a heuristic algorithm. I think even a heuristic one, it should be with a complexity of running time.
options = optimoptions(@intlinprog,'RelativeGapTolerance',0.2,'Display','iter')
[x,fval]=intlinprog(f,iint,A,b,[],[],lb,ub,[],options);
Settings:
AbsoluteGapTolerance: 1
Display: 'iter'
Heuristics: 'basic'

サインインしてコメントする。

回答 (1 件)

Alan Weiss 2021 年 11 月 26 日
It is well known that MILP is an NP-complete problem. See https://en.wikipedia.org/wiki/Integer_programming for an explanation. In other words, there is no known algorithm, including the intlinprog algorithm, that has a finishing time that is polynomial in the problem size.
Alan Weiss
MATLAB mathematical toolbox documentation
2 件のコメント表示非表示 1 件の古いコメント
Derya 2021 年 11 月 29 日
Hello Frank,
I realized that the options of intlinprog you mention above, specifically "Heuristics", may have made you believe that the solver uses just a "heuristic algorithm" to solve MILPs.
Actually, there are many procedures employed to solve an MILP. intlinprog is a solver that at the core uses a branch-and-bound algorithm. After pre-processing the user provided MILP model's LP relaxation, intlinprog applies a series of integer programming (IP) preprocessing and cut generation algorithms followed by attepts to find integer feasible solutions with different heuristics such as rounding and diving (See documentation for more information). After all these "sub" algorithms, the reduced LPs are solved within a branch-and-bound algorithm with the aim to close the gap between best found integer feasible solution and the bounds of the remaining relaxed LPs.
Knowing the emprical time complexity of a heuristic used at the beginning of the solution process will not provide you any useful information.
You may be considering a complexity bound for the branch and bound algorithm. Then check out this discussion: https://rjlipton.wpcomstaging.com/2012/12/19/branch-and-bound-why-does-it-work/
You may be trying to gauge the difficulty of an MILP. Then the following may be helpful: https://www.researchgate.net/post/How_to_measure_the_difficulty_of_a_Mixed-Linear_Integer_Programming_MILP_problem
Kind Regards,
Derya

サインインしてコメントする。

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!