Superadditive duality and convex hulls for mixed-integer conic optimization

We present an infinite family of linear valid inequalities for a mixed-integer conic program, and prove that these inequalities describe the convex hull of the feasible set when this set is bounded and described by integral data. The main element of our proof is to establish a new strong superadditive dual for mixed-integer conic programming … Read more

Large independent sets in Markov random graphs

\(\) Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well-studied for various classes of graphs. When it comes to random graphs, only the classical binomial random graph \(G_{n,p}\) has been analysed and shown to have largest independent sets of size \(\Theta(\log{n})\) w.h.p. This … Read more

Ordering integers under different permutations

\(\) The question of finding the largest integer contained between two given lists of integers is trivial when integer ordering is interpreted in its usual way. We propose a nontrivial variant wherein each ordering comparison is performed after integers have been mapped under some bijection, and analyze the computational complexity of our combinatorial problem under … Read more

Multilinear formulations for computing Nash equilibrium of multi-player matrix games

We present multilinear and mixed-integer multilinear programs to find a Nash equilibrium in multi-player strategic-form games. We compare the formulations to common algorithms in Gambit, and conclude that a multilinear feasibility program finds a Nash equilibrium faster than any of the methods we compare it to, including the quantal response equilibrium method, which is recommended … Read more

Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) problem with Uncertainties

The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategical fleet-sizing, tactical assignment, operational vehicle routing and scheduling subproblems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a two-stage stochastic mixed-integer linear programming model for … Read more

Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints

It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized … Read more

On strong duality, theorems of the alternative, and projections in conic optimization

A conic program is the problem of optimizing a linear function over a closed convex cone intersected with an affine preimage of another cone. We analyse three constraint qualifications, namely a Closedness CQ, Slater CQ, and Boundedness CQ (also called Clark- Duffin theorem), that are sufficient for achieving strong duality and show that the first … Read more

Extended formulations for convex hulls of some bilinear functions

We consider the problem of characterizing the convex hull of the graph of a bilinear function $f$ on the $n$-dimensional unit cube $[0,1]^n$. Extended formulations for this convex hull are obtained by taking subsets of the facets of the Boolean Quadric Polytope (BQP). Extending existing results, we propose the systematic study of properties of $f$ … Read more

On Lexicographic Approximations of Integer Programs

We use the lexicographic order to define a hierarchy of primal and dual bounds on the optimum of a bounded integer program. These bounds are constructed using lex maximal and minimal feasible points taken under different permutations. Their strength is analyzed and it is shown that a family of primal bounds is tight for any … Read more

Error bounds for monomial convexification in polynomial optimization

Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of $[0,1]^n$. This … Read more