Neighborhood persistency of the linear optimization relaxation of integer linear optimization

DOI10.1007/978-3-031-18530-4_23MaRDI QIDQ6166912zbMATH OpenFDO

Authors Kei Kimura, Kotaro Nakayama

Publication date 3 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.04557

zbMATH Keywords

integer linear optimizationlinear optimizationpersistencyunit-two-variable-per-inequality system

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorial optimization (90C27)

Abstract: For an integer linear optimization (ILO) problem, persistency of its linear optimization (LO) relaxation is a property that for every optimal solution of the relaxation that assigns integer values to some variables, there exists an optimal solution of the ILO problem in which these variables retain the same values. Although persistency has been used to develop heuristic, approximation, and fixed-parameter algorithms for special cases of ILO, its applicability remains unknown in the literature. In this paper we reveal a maximal subclass of ILO such that its LO relaxation has persistency. Specifically, we show that the LO relaxation of ILO on unit-two-variable-per-inequality (UTVPI) systems has persistency and is (in a certain sense) maximal among such ILO. Our persistency result generalizes the results of Nemhauser and Trotter, Hochbaum et al., and Fiorini et al. Even more, we propose a stronger property called emph{neighborhood persistency} and show that the LO relaxation of ILO on UTVPI systems in general has this property. Using this stronger result, we obtain a fixed-parameter algorithm (where the parameter is the solution size) and another proof of two-approximability for ILO on UTVPI systems where objective functions and variables are non-negative.

Recommendations

• Persistency in 0-1 polynomial programming
• Persistency of linear programming relaxations for the stable set problem
• Persistency of linear programming relaxations for the stable set problem
• Persistency in quadratic 0-1 optimization
• Integer Programming: Optimization and Evaluation Are Equivalent

Cites work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combining traditional map labeling with boundary labeling
• Disjoint homotopic paths and trees in a planar graph
• Faster parameterized algorithms using linear programming
• Frontiers of Combining Systems
• Half-integrality, LP-branching, and FPT algorithms
• Minimum Clique Cover in Claw-Free Perfect Graphs and the Weak Edmonds-Johnson Property
• Network flows. Theory, algorithms, and applications.
• On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
• Solving min ones 2-SAT as fast as vertex cover
• Sub-polyhedral scheduling using (unit-)two-variable-per-inequality polyhedra
• The octagon abstract domain
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Vertex packings: Structural properties and algorithms

Cited in

(2)

• Exploring relaxation induced neighborhoods to improve MIP solutions
• Neighborhood persistency of the linear optimization relaxation of integer linear optimization

This page was built for publication: Neighborhood persistency of the linear optimization relaxation of integer linear optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166912)