disjunctions

Mathematical Programming Formulations for Piecewise Polynomial Functions

  • Bjarne Grimstad
  • Brage Rugstad Knudsen
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    This paper studies mathematical programming formulations for solving optimization problems with piecewise polynomial (PWP) constraint functions. We elaborate on suitable polynomial bases as a means of efficiently representing PWPs in mathematical programs, comparing and drawing connections between the monomial basis, the Bernstein basis, and B-splines. The theory is presented for both continuous and semi-continuous PWPs. … Read more

    Disjunctive cuts for non-convex MINLP

  • Pietro Belotti
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Mixed Integer Nonlinear Programming (MINLP) problems present two main challenges: the integrality of a subset of variables and nonconvex (nonlinear) objective function and constraints. Many exact solvers for MINLP are branch-and-bound algorithms that compute a lower bound on the optimal solution using a linear programming relaxation of the original problem. In order to solve these … Read more

    On complexity of Selecting Branching Disjunctions in Integer Programming

  • Ashutosh Mahajan
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Branching is an important component of branch-and-bound algorithms for solving mixed integer linear programs. We consider the problem of selecting, at each iteration of the branch-and-bound algorithm, a general branching disjunction of the form $“\pi x \leq \pi_0 \vee \pi x \geq \pi_0 + 1”$, where $\pi, \pi_0$ are integral. We show that the problem … Read more