Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using … Read more
In this paper, we consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is … Read more
Concave Mixed-Integer Quadratic Programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an ε-approximate solution to a Concave Mixed-Integer Quadratic Programming problem. The running time of the proposed algorithm is polynomial in the size of the problem … Read more
We introduce a new technique to generate good feasible points of mixed-integer nonlinear optimization problems. It makes use of the so-called inner parallel set of the relaxed feasible set, which was employed in O. Stein, Error bounds for mixed integer linear optimization problems, Mathematical Programming, Vol. 156 (2016), 101-123, as well as O. Stein, Error … Read more
We explore the lifting question in the context of cut-generating functions. Most of the prior literature on lifting for cut-generating functions focuses on which cut-generating functions have the unique lifting property. Here we develop a general theory for under- standing how to do lifting for cut-generating functions which do not have the unique lifting property. … Read more
We present a framework for constructing small, strong mixed-integer formulations for disjunctive constraints. Our approach is a generalization of the logarithmically-sized formulations of Vielma and Nemhauser for SOS2 constraints, and we offer a complete characterization of its expressive power. We apply the framework to a variety of disjunctive constraints, producing novel, small, and strong formulations … Read more
We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer … Read more
In this paper, I view and present the multiobjective discrete optimisation problem as a particular case of disjunctive programming where one seeks to identify efficient solutions from within a disjunction formed by a set of systems. The proposed approach lends itself to a simple yet effective iterative algorithm that is able to yield the set … Read more
We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for … Read more
We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory–Johnson model which is not extreme, but which is not a convex combination of other piecewise linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more