In this paper, we extend a recently proposed scenario decomposition algorithm (Ahmed (2013)) for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the … Read more
Dantzig-Wolfe reformulation of an integer program convexifies a subset of the constraints, which yields an extended formulation with a potentially stronger linear programming (LP) relaxation. We would like to better understand the strength of such reformulations in general. As a first step we investigate the classical edge formulation for the stable set problem. We characterize … Read more
Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an $L_p$-norm ($0 < p < 1$) regularization ... Read more
We investigate a new class of congestion games, called Totally Unimodular Congestion Games, in which the strategies of each player are expressed as binary vectors lying in a polyhedron defined using a totally unimodular constraint matrix and an integer right-hand side. We study both the symmetric and the asymmetric variants of the game. In the … Read more
In this paper we propose the problem of finding the cyclic sequence which best represents a set of cyclic sequences. Given a set of elements and a precedence cost matrix we look for the cyclic sequence of the elements which is at minimum distance from all the ranks when the permutation metric distance is the … Read more
This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these in- equalities. The result of this paper may contribute to the development of more efficient algorithms for the … Read more
We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more
A variety of formulations for the Travelling Salesman Problem as Mixed Integer Program have been proposed. They contain either non-binary variables or the number of constraints and variables is large. We want to give a new formulation that consists solely of binary variables; the number of variables and the number of constraints are of order … Read more
This paper is concerned with completely positive and semidefinite relaxations of quadratic programs with linear constraints and binary variables as presented by Burer. It observes that all constraints of the relaxation associated with linear constraints of the original problem can be accumulated in a single linear constraint without changing the feasible set of either the … Read more
Given a graph $G=(V,E)$ where $|V|=n$ and $|E|=m$. Graph partitioning problems on $G$ are to find a partition of the vertices in $V$ into clusters satisfying several additional constraints in order to minimize or maximize the number (or the weight) of the edges whose endnodes do not belong to the same cluster. These problems are … Read more