Approximation Algorithms for the Incremental Knapsack Problem via Disjunctive Programming

In the \emph{incremental knapsack problem} ($\IK$), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of $T$ periods and the capacity of the knapsack is $B_t$ in period $t$ for $t = 1, \ldots, T$. We are also given a set $S$ of $N$ items … Read more

Polynomial solvability of variants of the trust-region subproblem

The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the … Read more

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