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

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 个评论
显示无隐藏无

Frank Dou 2021-11-27

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 2021-11-29

编辑：Derya 2021-11-30

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

请先登录，再进行评论。