Distances between optimal solutions of mixed-integer programs

Joseph Paat, Robert Weismantel, Stefan Weltge

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

19 Zitate (Scopus)

Abstract

A classic result of Cook et al. (Math. Program. 34:251–264, 1986) bounds the distances between optimal solutions of mixed-integer linear programs and optimal solutions of the corresponding linear relaxations. Their bound is given in terms of the number of variables and a parameter Δ, which quantifies sub-determinants of the underlying linear inequalities. We show that this distance can be bounded in terms of Δ and the number of integer variables rather than the total number of variables. To this end, we make use of a result by Olson (J. Number Theory 1:8–10, 1969) in additive combinatorics and demonstrate how it implies feasibility of certain mixed-integer linear programs. We conjecture that our bound can be improved to a function that only depends on Δ, in general.

OriginalspracheEnglisch
Seiten (von - bis)455-468
Seitenumfang14
FachzeitschriftMathematical Programming
Jahrgang179
Ausgabenummer1-2
DOIs
PublikationsstatusVeröffentlicht - 1 Jan. 2020

Fingerprint

Untersuchen Sie die Forschungsthemen von „Distances between optimal solutions of mixed-integer programs“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren