{
  "id": "2103.09573",
  "version": "v1",
  "published": "2021-03-17T11:20:46.000Z",
  "updated": "2021-03-17T11:20:46.000Z",
  "title": "A Computational Study of Perspective Cuts",
  "authors": [
    "Ksenia Bestuzheva",
    "Ambros Gleixner",
    "Stefan Vigerske"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-17T11:20:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90-04",
      "90-08",
      "90C11",
      "90C26",
      "90C30",
      "90C57",
      "G.4"
    ],
    "keywords": [
      "computational study",
      "constraints reduces branch-and-bound tree sizes",
      "nonconvex constraints reduces branch-and-bound tree",
      "adding perspective cuts",
      "general mixed-integer nonlinear programs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}