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

29 visualizaciones (últimos 30 días)
Frank Dou
Frank Dou el 25 de Nov. de 2021
Editada: Derya el 30 de Nov. de 2021
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'

Respuestas (1)

Alan Weiss
Alan Weiss el 26 de Nov. de 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 comentarios
Frank Dou
Frank Dou el 27 de Nov. de 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 el 29 de Nov. de 2021
Editada: Derya el 30 de Nov. de 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

Iniciar sesión para comentar.

Categorías

Más información sobre Linear Programming and Mixed-Integer Linear Programming en Help Center y File Exchange.

Productos

Community Treasure Hunt

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

Start Hunting!

Translated by