polynomial optimisation

Matroid Optimisation Problems with Nested Non-linear Monomials in the Objective Function

  • Anja Fischer
  • Frank Fischer
  • S. Thomas McCormick
    • Categories 0-1 Programming, Graphs and Matroids, Polyhedra Tags , , , , ,

    Recently, Buchheim and Klein suggested to study polynomial-time solvable optimisation problems with linear objective functions combined with exactly one additional quadratic monomial. They concentrated on special quadratic spanning tree or forest problems. We extend their results to general matroid optimisation problems with a set of nested monomials in the objective function. The monomials are linearised … Read more

    Cutting Planes for RLT Relaxations of Mixed 0-1 Polynomial Programs

  • Franklin Djeumou Fomeni
  • Konstantinos Kaparis
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , ,

    The Reformulation-Linearization Technique (RLT), due to Sherali and Adams, can be used to construct hierarchies of linear programming relaxations of mixed 0-1 polynomial programs. As one moves up the hierarchy, the relaxations grow stronger, but the number of variables increases exponentially. We present a procedure that generates cutting planes at any given level of the … Read more

    Non-Convex Mixed-Integer Nonlinear Programming: A Survey

  • Samuel Burer
  • Adam N. Letchford
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , , ,

    A wide range of problems arising in practical applications can be formulated as Mixed-Integer Nonlinear Programs (MINLPs). For the case in which the objective and constraint functions are convex, some quite effective exact and heuristic algorithms are available. When non-convexities are present, however, things become much more difficult, since then even the continuous relaxation is … Read more