intlinprog函数的算法是什么？how to transfer 'intlinprog function' into algorithm expression?

想请教一下intlinprog函数的核心算法是什么，或者有哪些算法，论文的模型是0-1混合整数线性规划模型，需要求解算法，希望各位大佬解答。

Answer 1

[Varun]

你好 贞 吴，

我会用英语回答你的问题。

Looks like you want to learn about the algorithm used by “intlinprog” function.

“intlinprog” uses following basic strategies to solve mixed-integer linear programs. “intlinprog” can solve the problem in any of the stages. If it solves the problem in a stage, “intlinprog” does not execute the later stages.

Algorithm Overview:

1. Reduce the problem size using Linear Program Preprocessing.
2. Solve an initial relaxed (non-integer) problem using Linear Programming.
3. Perform Mixed-Integer Program Preprocessing to tighten the LP relaxation of the mixed-integer problem.
4. Try Cut Generation to further tighten the LP relaxation of the mixed-integer problem.
5. Try to find integer-feasible solutions using heuristics.
6. Use a Branch and Bound algorithm to search systematically for the optimal solution. This algorithm solves LP relaxations with restricted ranges of possible values of the integer variables. It attempts to generate a sequence of updated bounds on the optimal objective function value.

I have extracted this algorithm from the MathWorks’s documentation on “Mixed-Integer Linear Programming (MILP) Algorithms”. Please refer it below to learn in detail:

https://www.mathworks.com/help/optim/ug/mixed-integer-linear-programming-algorithms.html

Hope it helps.