Neighborhood persistency of the linear optimization relaxation of integer linear optimization
Kei Kimura  1, *@  , Kotaro Nakayama  2  
1 : Kyushu University
2 : Oplan Incorporated
* : Corresponding author

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. In this paper, we propose a stronger property called neighborhood persistency and show that the LO relaxation of ILO on unit-two-variable-per-inequality (UTVPI) systems is a maximal class of ILO such that its LO relaxation has (neighborhood) persistency. Our result implies fixed-parameter tractability and two-approximability for a special ILO on UTVPI systems.


Online user: 1 Privacy
Loading...