A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2016
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911581825138688 |
|---|---|
| author | Diaby, Moustapha |
| author_facet | Diaby, Moustapha |
| contents | Background: Combinatorial optimization problems (COPs) are central to Logistics and Supply Chain decision making, yet their NP-hardness prevents exact optimal solutions in reasonable time. Methods: 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 Θ(m^9) variables and Θ(m^8) constraints, where m 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). Results: Because the proposed LP model is polynomial-sized and there exist polynomial-time algorithms for solving LPs, it affirms "P = NP." 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 robutness relative to standard network flow models. Conclusiuons: Overall, tyhe 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 lrage-scale Logistics and other COP-intensive applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1610_00353 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems Diaby, Moustapha Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics Optimization and Control Background: Combinatorial optimization problems (COPs) are central to Logistics and Supply Chain decision making, yet their NP-hardness prevents exact optimal solutions in reasonable time. Methods: 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 Θ(m^9) variables and Θ(m^8) constraints, where m 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). Results: Because the proposed LP model is polynomial-sized and there exist polynomial-time algorithms for solving LPs, it affirms "P = NP." 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 robutness relative to standard network flow models. Conclusiuons: Overall, tyhe 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 lrage-scale Logistics and other COP-intensive applications. |
| title | A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems |
| topic | Data Structures and Algorithms Computational Complexity Discrete Mathematics Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/1610.00353 |