The running time complexity of Mixed-integer linear programming (MILP)?
35 views (last 30 days)
Show older comments
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.
So I set according to https://www.mathworks.com/help/optim/ug/intlinprog.html#btv2x05
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'
0 Comments
Answers (1)
Alan Weiss
on 26 Nov 2021
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 Comments
Derya
on 29 Nov 2021
Edited: Derya
on 30 Nov 2021
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
See Also
Categories
Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!