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.
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.
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.
A chance constrained problem involves a set of scenario constraints from which a small subset can be violated. Existing works typically consider a mixed integerprogramming (MIP) formulation of this problem by introdu...
详细信息
ISBN:
(纸本)9783319334615;9783319334608
A chance constrained problem involves a set of scenario constraints from which a small subset can be violated. Existing works typically consider a mixed integerprogramming (MIP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MIP formulation have been developed. In this paper we consider a family of cuts for chance constrained problems in the original space rather than those in the extended space of the MIP reformulation. these cuts, known as quantile cuts, can be viewed as a projection of the well known family of mixing inequalities for the MIP reformulation, onto the original problem space. We show the following results regarding quantile cuts: (i) the closure of all quantile cuts is a polyhedral set;(ii) separation of quantile cuts is in general NP-hard;(iii) successive application of quantile cut closures achieves the convex hull of the chance constrained problem in the limit;and (iv) in the pure integer setting this convergence is finite.
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.
We give a new, algorithmic proof for the maximum even factor formula which can be converted into a polynomial time combinatorial algorithm to solve the maximum even factor problem. In several aspects, the approach is ...
详细信息
ISBN:
(纸本)3540261990
We give a new, algorithmic proof for the maximum even factor formula which can be converted into a polynomial time combinatorial algorithm to solve the maximum even factor problem. In several aspects, the approach is similar to Edmonds' Matching Algorithm, but there is a significant difference.
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.
this book constitutes the proceedings of the 16thinternationalconference on integerprogramming and combinatorialoptimization, ipco 2013, held in Valparaíso, Chile, in March 2013. the 33 full papers presented ...
详细信息
ISBN:
(数字)9783642366949
ISBN:
(纸本)9783642366932
this book constitutes the proceedings of the 16thinternationalconference on integerprogramming and combinatorialoptimization, ipco 2013, held in Valparaíso, Chile, in March 2013. the 33 full papers presented were carefully reviewed and selected from 98 submissions. the conference is a forum for researchers and practitioners working on various aspects of integerprogramming and combinatorialoptimization withthe aim to present recent developments in theory, computation, and applications. the scope of ipco is viewed in a broad sense, to include algorithmic and structural results in integerprogramming and combinatorialoptimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.
暂无评论