The behavior of enumeration-based programs for solving MINLPs depends at least in part on the quality of the bounds on the optimal value and of the feasible solutions found. We consider MINLP problems with linear constraints. The convex hull relaxation (CHR) is a special case of the primal relaxation (Guignard 1994, 2007) that is very … Read more
The paper describes a new primal relaxation (PR) for computing bounds on nonlinear integer programming (NLIP) problems. It is a natural extension to NLIP problems of the geometric interpretation of Lagrangean relaxation presented by Geoffrion (1974) for linear problems, and it is based on the same assumption that some constraints are complicating and are treated … Read more
The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which … Read more
Bound tightening is an important component of algorithms for solving nonconvex Mixed Integer Nonlinear Programs. A {\em probing} algorithm is a bound-tightening procedure that explores the consequences of restricting a variable to a subinterval with the goal of tightening its bounds. We propose a variant of probing where exploration is based on iteratively applying a … Read more
In this paper, we study properties of general closed convex sets that determine the closed-ness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results … Read more
In this work, we propose a global optimization approach for mixed-integer programming problems. To this aim, we preliminarily de ne an exact penalty algorithm model for globally solving general problems and we show its convergence properties. Then, we describe a particular version of the algorithm that solves mixed integer problems. CitationDIS Technical Report n. 17, 2010.ArticleDownload … Read more
We consider the problem of minimizing a continuously differentiable function of several variables subject to simple bound constraints where some of the variables are restricted to take integer values. We assume that the first order derivatives of the objective function can be neither calculated nor approximated explicitly. This class of mixed integer nonlinear optimization problems … Read more
We describe a computationally effective method for generating disjunctive inequalities for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs, and in the limit will generate an inequality as strong as can be produced by the cut-generating nonlinear program suggested by Stubbs and Mehrotra. Using this procedure, we … Read more
We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints which arise naturally in various real-world applications such as portfolio selection and subset selection in regression. We propose a new semidefinite program (SDP) approach for computing the “best” diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation. We … Read more
In this paper, we show that the Chatal-Gomory closure of a compact convex set is a rational polytope. This resolves an open question discussed in Schrijver 1980 and generalizes the same result for the case of rational polytopes (Schrijver 1980), rational ellipsoids (Dey and Vielma 2010) and strictly convex sets (Dadush et. al 2010). In … Read more