A computational study of perspective cuts
From MaRDI portal
Publication:6062884
Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04) Experimental work for problems pertaining to operations research and mathematical programming (90-05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Mixed integer programming (90C11) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
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.
Recommendations
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Lift-and-project cuts for mixed integer convex programs
- Perspective reformulation and applications
- A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes
- SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
Cites work
- A branch-and-cut method for 0-1 mixed convex programming
- A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes
- A computationally useful algebraic representation of nonlinear disjunctive convex sets using the perspective function
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- Alternating current optimal power flow with generator selection
- Approximated perspective relaxations: a project and lift approach
- Benchmarking optimization software with performance profiles.
- Convex envelopes generated from finitely many compact convex sets
- Convex extensions and envelopes of lower semi-continuous functions
- Convex programming for disjunctive convex optimization
- Convex relaxations for quadratic on/off constraints and applications to optimal transmission switching
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Disjunctive Programming
- Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
- Generalized convex disjunctive programming: Nonlinear convex hull relaxation
- Improving the approximated projected perspective reformulation by dual information
- Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach
- MINLPLib -- a collection of test models for mixed-integer nonlinear programming
- Mixed integer nonlinear programs featuring ``on/off constraints: convex analysis and applications
- Mixed-integer nonlinear programs featuring ``on/off constraints
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulation and applications
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Projected perspective reformulations with applications in design problems
- QPLIB: a library of quadratic programming instances
- SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
- Strong formulations for conic quadratic optimization with indicator variables
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
- The Cutting-Plane Method for Solving Convex Programs
- The reformulation of two mixed integer programming problems
Cited in
(2)
This page was built for publication: A computational study of perspective cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6062884)
