{
  "id": "1507.08703",
  "version": "v1",
  "published": "2015-07-30T22:28:02.000Z",
  "updated": "2015-07-30T22:28:02.000Z",
  "title": "Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions",
  "authors": [
    "Natashia Boland",
    "Thomas Kalinowski",
    "Fabian Rigterink"
  ],
  "categories": [
    "math.OC",
    "math.CO"
  ],
  "abstract": "We investigate how well the graph of a bilinear function $b:[0,1]^n\\to\\reals$ can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number $c$ such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most $c$ times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor $c$ cannot be bounded by a constant independent of $n$. More precisely, we show that for a random bilinear function $b$ we have asymptotically almost surely $c\\geqslant\\sqrt n/4$. In addition we characterize the functions $b$ such that the McCormick relaxation is equal to the convex hull.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-07-30T22:28:02.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "convex hull",
      "random bilinear function",
      "mccormick relaxation approach",
      "convex lower bounding functions",
      "concave upper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}