A Θ(<i>m</i>⁹) Ternary Minimum-Cost Network Flow LP Model of the Assignment Problem Polytope, with Applications to Hard Combinatorial Optimization Problems

<i>Background:</i> Combinatorial optimization problems (COPs) are central to Logistics and Supply Chain decision making, yet their NP-hardness prevents exact optimal solutions in reasonable time. <i>Methods:</i> This work addresses that limitation by developing a novel ternary network flow linear programming (LP) model of the assignment problem (AP) polytope. The model is very large scale (with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Θ</mi><mo>(</mo><msup><mi>m</mi><mn>9</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> variables and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="sans-serif">Θ</mi><mo>(</mo><msup><mi>m</mi><mn>8</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> constraints, where <i>m</i> is the number of assignments). Although not intended to compete with conventional two-dimensional formulations of the AP with respect to solution procedures, it enables hard COPs to be solved exactly as “strict” (integrality requirements-free) LPs through simple transformations of their cost functions. Illustrations are given for the quadratic assignment problem (QAP) and the traveling salesman problem (TSP). <i>Results:</i> Because the proposed LP model is polynomial-sized and there exist polynomial-time algorithms for solving LPs, it affirms “<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>P</mi><mo>=</mo><mi>N</mi><mi>P</mi></mrow></semantics></math></inline-formula>.” A separable substructure of the model shows promise for practical-scale instances due to its suitability for large-scale optimization techniques such as Dantzig–Wolfe Decomposition, Column Generation, and Lagrangian Relaxation. The formulation also has greater robustness relative to standard network flow models. <i>Conclusions:</i> Overall, the approach provides a systematic, modeling-barrier-free framework for representing NP-complete problems as polynomial-sized LPs, with clear theoretical interest and practical potential for medium to large-scale Logistics and other COP-intensive applications.