speaking, my research focuses on theory and implementation of
high-performance optimization algorithms.
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 and DTRA. 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
- 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.