Optimization Online


Disjunctive cuts for non-convex MINLP

Pietro Belotti (pbelott***at***clemson.edu)

Abstract: 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 problems to optimality, disjunctions can be used to partition the solution set or to obtain strong lower bounds on the optimal solution of the problem. In the MINLP context, the use of disjunctions for branching has been subject to intense research, while the practical utility of disjunctions as a means of generating valid linear inequalities has attracted some attention only recently. We describe an application to MINLP of a well-known separation method for disjunctive cuts that has shown to be very effective in Mixed Integer Linear Programming (MILP). As the experimental results show, this application obtains encouraging results in the MINLP case even when a simple separation method is used.

Keywords: Disjunctions, MINLP, Couenne, Disjunctive cuts.

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 07/29/2009
Entry Accepted: 07/30/2009
Entry Last Modified: 03/23/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society