Distances between optimal solutions of mixed-integer programs

• 成果类型: Article
• 署名作者: Paat, Joseph; Weismantel, Robert; Weltge, Stefan
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Munich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1323-z
• 发表日期: 2020
• 页码: 455-468
• 关键词: proximity

摘要

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 Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \varDelta $$\end{document}, which quantifies sub-determinants of the underlying linear inequalities. We show that this distance can be bounded in terms of Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \varDelta $$\end{document} 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 Delta\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \varDelta $$\end{document}, in general.