Tightening simple mixed-integer sets with guaranteed bounds
We extend work on generating relaxations of simple sets with guaranteed bounds. CitationUnpublished. Columbia University, July 2008.ArticleDownload View PDF
Daniel Bienstock
Experiments in Robust Portfolio Optimization
We present experimental results on portfolio optimization problems with return errors under the robust optimization framework. We use several a histogram-like model for return deviations, and a model that allows correlation among errors, together with a cutting-plane algorithm which proves effective for large, real-life data sets. CitationColumbia Center for Financial Engineering Report 2007-01 Columbia University, … Read more
Approximate formulations for 0-1 knapsack sets
A classical theorem in Combinatorial Optimization proves the existence of fully polynomial- time approximation schemes for the knapsack problem. In a recent paper, Van Vyve and Wolsey ask whether for each 0 < epsilon ≤ 1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables and/or 1/epsilon ... Read more
Computing robust basestock levels
This paper considers how to optimally set the basestock level for a single buffer when demand is uncertain, in a robust framework. We present a family of algorithms based on decomposition that scale well to problems with hundreds of time periods, and theoretical results on more general models. CitationCORC report TR-2005-09, Columbia University, November 2005ArticleDownload … Read more
Using mixed-integer programming to solve power grid blackout problems
We consider optimization problems related to the prevention of large-scale cascading blackouts in power transmission networks subject to multiple scenarios of externally caused damage. We present computation with networks with up to 600 nodes and 827 edges, and many thousands of damage scenarios. CitationCORC Report TR-2005-07, Columbia UniversityArticleDownload View PDF
Faster approximation algorithms for packing and covering problems
We adapt a method due to Nesterov so as to obtain an algorithm for solving block-angular fractional packing or covering problems to relative tolerance epsilon, while using a number of iterations that grows polynomially in the size of the problem and whose dependency on epsilon is proportional to 1/epsilon. CitationCORC report TR-2004-09, Computational Optimization Research … Read more
Approximate fixed-rank closures of set covering problems
We show that for any fixed rank, the closure of a set covering problem (and related problems) can be approximated in polynomial time — we can epsilon-approximate any linear program over the closure in polynomial time. CitationCORC report TR-2003-01, Computational Optimization Research Center, Columbia UniversityArticleDownload View PDF