Computing Feasible Points for Binary MINLPs with MPECs

Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use … Read more

An Exact Algorithm for the Partition Coloring Problem

We study the Partition Coloring Problem (PCP), a generalization of the Vertex Coloring Problem where the vertex set is partitioned. The PCP asks to select one vertex for each subset of the partition in such a way that the chromatic number of the induced graph is minimum. We propose a new Integer Linear Programming formulation … Read more

Mixed-integer linear representability, disjunctions, and Chvatal functions — modeling implications

Jeroslow and Lowe gave an exact geometric characterization of subsets of $\mathbb{R}^n$ that are projections of mixed-integer linear sets, also known as MILP-representable or MILP-R sets. We give an alternate algebraic characterization by showing that a set is MILP-R {\em if and only if} the set can be described as the intersection of finitely many … Read more

Second-order cone programming formulation for two player zero-sum game with chance constraints

We consider a two player finite strategic zero-sum game where each player has stochastic linear constraints. We formulate the stochastic constraints of each player as chance constraints. We show the existence of a saddle point equilibrium if the row vectors of the random matrices, defining the stochastic constraints of each player, are elliptically symmetric distributed … Read more

On Dantzig figures from graded lexicographic orders

We construct two families of Dantzig figures, which are $d$-dimensional polytopes with $2d$ facets and an antipodal vertex pair, from convex hulls of initial subsets for the graded lexicographic (grlex) and graded reverse lexicographic (grevlex) orders on $\mathbb{Z}^{d}_{\geq 0}$. These polytopes have the same number of vertices $O(d^2)$ and the same number of edges $O(d^3)$, … Read more

The structure of the infinite models in integer programming

The infinite models in integer programming can be described as the convex hull of some points or as the intersection of half-spaces derived from valid functions. In this paper we study the relationships between these two descriptions. Our results have implications for finite dimensional corner polyhedra. One consequence is that nonnegative continuous functions suffice to … Read more

Fixing and extending some recent results on the ADMM algorithm

We first point out several flaws in the recent paper {\it [R. Shefi, M. Teboulle: Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim. 24, 269–297, 2014]} that proposes two ADMM-type algorithms for solving convex optimization problems involving compositions with linear operators and show … Read more

Permutations in the factorization of simplex bases

The basis matrices corresponding to consecutive iterations of the simplex method only differ in a single column. This fact is commonly exploited in current LP solvers to avoid having to compute a new factorization of the basis at every iteration. Instead, a previous factorization is updated to reflect the modified column. Several methods are known … Read more

On the Convergence of Asynchronous Parallel Iteration with Arbitrary Delays

Recent years have witnessed the surge of asynchronous parallel (async-parallel) iterative algorithms due to problems involving very large-scale data and a large number of decision variables. Because of asynchrony, the iterates are computed with outdated information, and the age of the outdated information, which we call \emph{delay}, is the number of times it has been … Read more