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
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
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
In this paper, we propose a new primal-dual algorithm for minimizing f(x)+g(x)+h(Ax), where f, g, and h are convex functions, f is differentiable with a Lipschitz continuous gradient, and A is a bounded linear operator. It has some famous primal-dual algorithms for minimizing the sum of two functions as special cases. For example, it reduces … Read more
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
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
In this study, we develop heuristic methods to solve unimodular quadratic programming (UQP) approximately, which is known to be NP-hard. UQP-type problems appear naturally in radar waveform design and active sensing applications. In the UQP framework, we optimize a sequence of complex variables with unit modulus by maximizing a quadratic function. To solve the UQP … Read more
The university course timetabling problem deals with the task of scheduling lectures of a set of university courses into a given number of rooms and time periods, taking into account various hard and soft constraints. The goal of the International Timetabling Competitions ITC2002 and ITC2007 was to establish models for comparison that cover the most … Read more
This paper describes a unified approach for solving Box-Constrained Optimization Problems (BCOP) in Euclidian spaces. The variables may be either continuous or discrete; in which case, they range on a grid of isolated points regularly spaced. For the continuous case, convergence is shown under standard assumptions; for the discrete case, slight modifications ensure that the … Read more
Moment-sum-of-squares hierarchies of semidefinite programs can be used to approximate the volume of a given compact basic semialgebraic set $K$. The idea consists of approximating from above the indicator function of $K$ with a sequence of polynomials of increasing degree $d$, so that the integrals of these polynomials generate a convergence sequence of upper bounds … Read more