My research

I am currently concentrating on four topics:

- Using optimization
techniques for diagnosing hidden vulnerabilities in electrical power
grids. Several national-scale blackouts took place in
the recent past, with significant consequences. More such
blackouts can be expected. Even though large-scale blackouts are
quite rare, when they do happen the impact can be dire. Blackouts
are rare because modern power grids are robust; yet vulnerabilities do
exist. The search for hidden vulnerabilities, roughly speaking,
embodies finding an instance where a limited amount of damage can cause
a grid to collapse. It is important to frame the search for such
vulnerabilities in a completely agnostic manner. We are using
techniques reminiscent of robust optimization in order to develop
computational tools that effectively incorporate the
physics of power networks and scale well to large cases. This work is
currently funded by the U.S. Department of Energy. Further
material available
**here.**

- Fundamental methodologies for integer programming. We are studying techniques for provably tightening formulations of mixed-integer programs. Here, 'provably' means that we seek guarantees (e.g. error bounds). Thus, in an ideal setting an improved formulation is polynomially large and guarantees a 'small' approximation error. Our primary technique in this context is the use of carefully selected combinatorial disjunctions. Another focal area involves the use of eigenvalue techniques in order to tighten formulations for convex objective, nonconvex (but possibly noncombinatorial) optimization problems. Problems of this type abound in engineering applications, where the convex objective is often a measure of "error" or "energy", while the underlying physics impose significant nonconvexities. This work is funded by ONR.

- Robust epidemic models. An important application we are currently investigating involves 'gaming' an epidemic: clasical models for the evolution of an epidemic are based on several noisy parameters, in particular the infection rate. A decision-maker who wishes to allocate scarce resources so as to manage the impact of an epidemic would have to take difficult-to-define uncertainty into account. In our work we take the robust optimization outlook; we have developed computationally practicable versions of Benders' algorithm, which in this context can be interpretated as a game between an optimizer and the adversary.

- Efficient solutions of massive linear programs related to constrained scheduling problems. Motivated by problems arising in the mining industry, we consider precedence-constrained, multi-period production scheduling problems with side constraints. The side constraints arise from the need to assign production to a given set of facilities with general constraints. The precedence specify a partial order among the jobs to be processed. In practice this gives rise to optimization problems with hundreds of millions of constraints and variables. Without the side constraints the problem can be modeled as a maximum weight closure problem, and thus, solved as a min-cut problem; the side constraints, however, render the problem strongly NP-complete. We have developed a new solution technique for the LP-relaxation of the problem which enable us to solve the largest practical instances, to proved optimality, in few iterations and short CPU time. This work is partially funded by a gift from BHP Billiton, Inc, and the ONR.