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

29 views (last 30 days)
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'

Answers (1)

Alan Weiss
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
Frank Dou
Frank Dou on 27 Nov 2021
Yes, SCP is NP-hard.
But using the heuristic algorithm, is there a empirical time complexity?
I think it also follows an approximate exponential complexity?
Derya
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

Sign in to comment.

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!