My research

• 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.