Generally, it is conjectured that problems in the same class as the Symmetric Traveling Salesman Problem (STSP) are difficult problems. Pedigrees are combinatorial objects defined and studied by the author, and they are in \(1-1\) correspondence with the symmetric Traveling salesman tours. Recently the author published the book, entitled Pedigree Polytopes ([1]), bringing together known results on pedigree polytopes, in addition to showing that membership in pedigree polytopes can be checked by implementing a strongly polynomial framework. This article explains the framework and outlines how the author has a Python implementation of the framework for checking the following: Given \(X \in Q^{\tau _{n}}\) , is \(X \in conv(P_{n})\) , where \(\tau _{n} = \left( {\begin{array}{c}n\\ 3\end{array}}\right) -1,\) is the cardinality of the set, \(\{ (i, j, k) | 1 \le i < j < k, k = 4, \ldots , n\},\) and \(conv(P_{n})\) is the convex hull of pedigrees for a given \(n > 3.\) This implementation uses open-source Python libraries like NetworkX ([7]) and a linear programming package, like Gurobi ([5]). The framework given in the book shows that the framework can be implemented in strongly polynomial time using Tardos’s approach ([11]). The framework given by Tardos is theoretical, as cautioned by Tardos, “probably should be considered a purely theoretical contribution.” ([11, p. 251]. Future implementations will deploy algorithms for solving a combinatorial LP problem as a subroutine. This talk on this new beginning is fitting with the occasion of celebrating DC Programming, which opened new ways to solve difficult integer and combinatorial optimization problems forty years ago.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Solving Difficult Combinatorial Optimization Problems Efficiently - A New Framework

  • Tiru S. Arthanari

摘要

Generally, it is conjectured that problems in the same class as the Symmetric Traveling Salesman Problem (STSP) are difficult problems. Pedigrees are combinatorial objects defined and studied by the author, and they are in \(1-1\) correspondence with the symmetric Traveling salesman tours. Recently the author published the book, entitled Pedigree Polytopes ([1]), bringing together known results on pedigree polytopes, in addition to showing that membership in pedigree polytopes can be checked by implementing a strongly polynomial framework. This article explains the framework and outlines how the author has a Python implementation of the framework for checking the following: Given \(X \in Q^{\tau _{n}}\) , is \(X \in conv(P_{n})\) , where \(\tau _{n} = \left( {\begin{array}{c}n\\ 3\end{array}}\right) -1,\) is the cardinality of the set, \(\{ (i, j, k) | 1 \le i < j < k, k = 4, \ldots , n\},\) and \(conv(P_{n})\) is the convex hull of pedigrees for a given \(n > 3.\) This implementation uses open-source Python libraries like NetworkX ([7]) and a linear programming package, like Gurobi ([5]). The framework given in the book shows that the framework can be implemented in strongly polynomial time using Tardos’s approach ([11]). The framework given by Tardos is theoretical, as cautioned by Tardos, “probably should be considered a purely theoretical contribution.” ([11, p. 251]. Future implementations will deploy algorithms for solving a combinatorial LP problem as a subroutine. This talk on this new beginning is fitting with the occasion of celebrating DC Programming, which opened new ways to solve difficult integer and combinatorial optimization problems forty years ago.