Mathematical modelling languages such as AMPL, GAMS, and Xpress-MP enable mathematical models such as mixed-integer linear programmes (MILPs) to be expressed clearly for solution in solvers such as CPLEX, MINOS and Gurobi. However some models are sufficiently difficult that they cannot be solved using “out-of-the-box” solvers, and customisation of the solver framework to exploit model-specific … Read more
Quadratic Convex Reformulation (QCR) is a technique that was originally proposed for quadratic 0-1 programs, and then extended to various other problems. It is used to convert non-convex instances into convex ones, in such a way that the bound obtained by solving the continuous relaxation of the reformulated instance is as strong as possible. In … Read more
Given an undirected graph and a positive integer k, the maximum k-colorable subgraph problem consists of selecting a k-colorable induced subgraph of maximum cardinality. The natural integer programming formulation for this problem exhibits two kinds of symmetry: arbitrarily permuting the color classes and/or applying a non-trivial graph automorphism gives equivalent solutions. It is well known … Read more
This paper is concerned with the improved constraints handling in mixed-integer optimization problems. The novel element is the reduction of the number of binary variables used for expressing the complement of a convex (polytopic) region. As a generalization, the problem of representing the complement of a possibly non-connected union of such convex sets is detailed. … Read more
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
The classical column generation is based on optimal solutions of the restricted master problems. This strategy frequently results in an unstable behaviour and may require an unnecessarily large number of iterations. To overcome this weakness, variations of the classical approach use interior points of the dual feasible set, instead of optimal solutions. In this paper, … 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