Cutting-planes for optimization of convex functions over nonconvex sets

Motivated by mixed-integer, nonlinear optimization problems, we derive linear inequality characterizations for sets of the form conv{(x, q ) \in R^d × R : q \in Q(x), x \in R^d – int(P )} where Q is convex and differentiable and P \subset R^d . We show that in several cases our characterization leads to polynomial-time … Read more

Models for managing the impact of an epidemic

In this paper we consider robust models of surge capacity plans to be deployed in the event of a flu pandemic. In particular, we focus on managing critical staff levels at organizations that must remain operational during such an event. We develop efficient procedures for managing emergency resources so as to minimize the impact of … Read more

Strong formulations for convex functions over nonconvex sets

In this paper we derive strong linear inequalities for sets of the form {(x, q) ∈ R^d × R : q ≥ Q(x), x ∈ R^d − int(P ) }, where Q(x) : R^d → R is a quadratic function, P ⊂ R^d and “int” denotes interior. Of particular but not exclusive interest is the … Read more

Optimal adaptive control of cascading power grid failures

We describe experiments with parallel algorithms for computing adaptive controls for attenuating power grid cascading failures. Citation Columbia University, 2010 Article Download View Optimal adaptive control of cascading power grid failures

A new LP algorithm for precedence constrained production scheduling

We present a number of new algorithmic ideas for solving LP relaxations of extremely large precedence constrained production scheduling problems. These ideas are used to develop an implementation that is tested on a variety of real-life, large scale instances; yielding optimal solutions in very practicable CPU time. Citation Unpublished. Columbia University, BHP Billiton, August 2009. … Read more

Eigenvalue techniques for proving bounds for convex objective, nonconvex programs

We describe techniques combining the S-lemma and computation of projected quadratics which experimentally yield strong bounds on the value of convex quadratic programs with nonconvex constraints Citation unpublished report, Columbia University, March 2009 Article Download View Eigenvalue techniques for proving bounds for convex objective, nonconvex programs

The N – k Problem in Power Grids: New Models, Formulations and Computation

Given a power grid modeled by a network together with equations describing the power flows, power generation and consumption, and the laws of physics, the so-called N – k problem asks whether there exists a set of k or fewer arcs whose removal will cause the system to fail. We present theoretical results and computation … Read more

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. Citation Columbia Center for Financial Engineering Report 2007-01 Columbia … 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