{
  "id": "1801.08751",
  "version": "v1",
  "published": "2018-01-26T10:51:51.000Z",
  "updated": "2018-01-26T10:51:51.000Z",
  "title": "Distances of optimal solutions of mixed-integer programs",
  "authors": [
    "Joseph Paat",
    "Robert Weismantel",
    "Stefan Weltge"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "A classic result of Cook et al. (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 $, which quantifies sub-determinants of the underlying linear inequalities. We show that this distance can be bounded in terms of $ \\Delta $ and the number of integer variables rather than the total number of variables. To this end, we make use of a result by Olson (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 $, in general.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-26T10:51:51.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "optimal solutions",
      "mixed-integer programs",
      "mixed-integer linear programs",
      "implies feasibility",
      "corresponding linear relaxations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}