convex underestimators

Spatial branch-and-bound for nonconvex separable piecewise linear optimization

  • Thomas Hübner
  • Akshay Gupte
  • Steffen Rebennack
    • Categories (Mixed) Integer Linear Programming, Global Optimization Tags , , , ,

    Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimisation, using special ordered sets and mixed integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm (sBB) … Read more

    On convex envelopes and underestimators for bivariate functions

  • Marco Locatelli
  • Fabio Schoen
    • Categories Global Optimization, Semi-definite Programming Tags , , ,

    In this paper we discuss convex underestimators for bivariate functions. We first present a method for deriving convex envelopes over the simplest two-dimensional polytopes, i.e., triangles. Next, we propose a technique to compute the value at some point of the convex envelope over a general two-dimensional polytope, together with a supporting hyperplane of the convex … Read more