A Polynomial Time Algorithm For 0-1 Integer Linear Programmings

Autor:	Zhang, G. Q.
Rok vydání:	2023
Předmět:	Mathematics - Optimization and Control G.1.6
Druh dokumentu:	Working Paper
Popis:	A polynomial-time algorithm for 0-1 integer linear programmings has been proposed. This method continues the classic idea of solving ILP with its LP relaxation. The innovation is that every constraint in the LP is reconstructed into a strong cut. Then the solution algorithm of a 0-1 ILP is developed based on the new constraints. Algorithmic complexity analysis shows that the proposed algorithm is a polynomial-time algorithm, which means that P=NP. Comment: After testing, this is not a polynomial time algorithm for 0-1 ILP. The reason is that the new constraints generated by arbitrarily finding r different AVs may not necessarily be equivalent to the original constraint.That is to say, it is currently not possible to generate a new constraint equivalent to the original constraint in polynomial time
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2302.06049 Zobrazit plný text záznamu View this record from Arxiv