Gomory-Chvatal cuts are prominent in integerprogramming. the Gomory-Chvatal closure of a polyhedron is the intersection of all half spaces defined by its Gomory-Chvatal cuts. In this paper, we show that it is NP-comp...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
Gomory-Chvatal cuts are prominent in integerprogramming. the Gomory-Chvatal closure of a polyhedron is the intersection of all half spaces defined by its Gomory-Chvatal cuts. In this paper, we show that it is NP-complete to decide whether the Gomory-Chvatal closure of a rational polyhedron is empty, even when this polyhedron contains no integer point. this implies that the problem of deciding whether the Gomory-Chvatal closure of a rational polyhedron P is identical to the integer hull of P is NP-hard. Similar results are also proved for the {-1, 0, 1}-cuts and {0, 1}-cuts, two special types of Gomory-Chvatal cuts with coefficients restricted in {-1, 0, 1} and {0, 1}, respectively.
We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. We propose a framework to build (sub-)symmetry-breaking inequalitie...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
We consider integer linear programs whose solutions are binary matrices and whose (sub-)symmetry groups are symmetric groups acting on (sub-)columns. We propose a framework to build (sub-)symmetry-breaking inequalities for such programs, by introducing one additional variable per sub-symmetry group considered. the proposed framework is applied to derive inequalities breaking both symmetries and sub-symmetries in the graph coloring problem and in the ramp constrained min-up/min-down unit commitment problem.
Consider a matroid where all elements are labeled with an element in Z. We are interested in finding a base where the sum of the labels is congruent to g (mod m). We show that this problem can be solved in (O) over ti...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Consider a matroid where all elements are labeled with an element in Z. We are interested in finding a base where the sum of the labels is congruent to g (mod m). We show that this problem can be solved in (O) over tilde (2(4m)nr(5/6)) time for a matroid with n elements and rank r, when m is either the product of two primes or a prime power. the algorithm can be generalized to all moduli and, in fact, to all abelian groups if a classic additive combinatorics conjecture by Schrijver and Seymour holds true. We also discuss the optimization version of the problem.
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs ...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs min{c.x : x is an element of P boolean AND Z(n)}, where P = {x is an element of R-n : Ax = b, x >= 0} is a polyhedron in the standard form determined by an integer m x n matrix A and an integer vector b. the main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of support of the optimal solutions corresponding to the vertices of the integer hull of P. Additionally, we obtain a new proximity bound that estimates the l(2)-distance from a vertex of P to its nearest integer point in the polyhedron P. the proofs make use of the results from the geometry of numbers and convex geometry.
One of the most famous conjectures in combinatorialoptimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to 4/3. For 40 years, the best kno...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
One of the most famous conjectures in combinatorialoptimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to 4/3. For 40 years, the best known upper bound was 1.5, due to Wolsey [Wol80]. Recently, Karlin, Klein, and Oveis Gharan [KKO22] showed that the max entropy algorithm for the TSP gives an improved bound of 1.5 - 10(-36). In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.
the Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that ass...
详细信息
ISBN:
(纸本)9783030457716;9783030457709
the Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them has the this property as well. We show that any stronger LP formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable-set polytope.
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of the...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
Given a factorable function f, we propose a procedure that constructs a concave underestimator of f that is tight at a given point. these underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.
Linear programming is a foundational tool for many aspects of integer and combinatorialoptimization. this work studies the complexity of solving linear programs exactly over the rational numbers through use of an ora...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
Linear programming is a foundational tool for many aspects of integer and combinatorialoptimization. this work studies the complexity of solving linear programs exactly over the rational numbers through use of an oracle capable of returning limited-precision LP solutions. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. Previous work has often considered oracles that provide solutions of an arbitrary specified precision. While this leads to polynomial-time algorithms, the level of precision required is often unrealistic for practical computation. In contrast, our work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.
Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate ...
ISBN:
(纸本)9783031598340;9783031598357
Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in a typical hub-and-spoke fashion. In practice, such consolidation requires parcel sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that it is NP-hard to determine whether a feasible sortation plan exists. We discuss several settings, where (near-) feasibility of a given sortation instance can be determined efficiently. the algorithms we propose are fast and build on combinatorial witness set type lower bounds that are reminiscent and extend those used in earlier work on degree-bounded spanning trees and arborescences.
We propose two simple polynomial-time algorithms to find a positive solution to Ax = 0. Both algorithms iterate between coordinate descent steps similar to von Neumann's algorithm, and rescaling steps. In both cas...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
We propose two simple polynomial-time algorithms to find a positive solution to Ax = 0. Both algorithms iterate between coordinate descent steps similar to von Neumann's algorithm, and rescaling steps. In both cases, either the updating step leads to a substantial decrease in the norm, or we can infer that the condition measure is small and rescale in order to improve the geometry. We also show how the algorithms can be extended to find a solution of maximum support for the system Ax = 0, x >= 0. this is an extended abstract. the missing proofs will be provided in the full version.
暂无评论