Value of Multi-Stage Stochastic Optimization in Power Systems
Day-ahead scheduling of electricity generation or unit commitment is
an important and challenging operational activity in power systems.
Increasing penetration of renewable technologies in recent years has
motivated addressing uncertainty in this already difficult
optimization problem. Existing approaches adopt a two-stage decision
structure, where the day-ahead commitment is decided before the
uncertainty is realized and the power dispatch is adapted to the
uncertainty. In the first part of this talk, we present theoretical
results on the value of multi-stage or dynamic generation scheduling
in risk-neutral and risk-averse settings. The second part of the talk
is on algorithmic developments. In particular, we present a Stochastic
Dual Dynamic Integer Programming (SDDiP) algorithm for multistage
stochastic unit commitment problems.
Universidad Adolfo Ibáñez
Large-scale Open Pit Mine Production-Scheduling
The central concern of strategic mine planning is the construction of
a tentative production schedule. This is a life-of-mine plan (20-50
years) specifying which part of a mineral deposit should be extracted,
when it should be extracted, and how it should be extracted so as to
maximize the net present value of the mining project (easily in the
hundreds of millions of dollars).
Strategic mine planning is a complex optimization problem made
daunting both by the great number of activities that must be scheduled
in time and the great uncertainty concerning key economic, geological
and operational parameters. Despite being a fairly standard problem
regularly faced my mining projects throughout the world, it has
received very little attention from the operations research community.
In this talk we describe our efforts modelling this problem as an
RCPSP (Resource Constrained Project Scheduling Problem), the
integer-programming techniques we have been using to tackle them, and
our experience working with Newmont and Barrick gold, the world’s
biggest gold producers.
This talk covers joint work with Andrea Brickey, Daniel Espinoza,
Barry King, Eduardo Moreno, Gonzalo Muñoz, Alexandra Newman and
Google and University of California, Berkeley
Recent progress in machine learning highlights at least two conceptual and technical challenges for optimization research. One is to understand how different model architectures---equivalent in expressivity---affect the difficulty of non-convex optimization. The other is how external criteria, such as out-of-sample generalization, interact with the choice of optimization algorithm. We discuss some emerging theory addressing these intriguing problems, while emphasizing the many challenges that remain.
Discrete Optimization and Network Analysis
Graphs or networks are everywhere and network analysis has garnered significant attention in diverse fields as
an effective tool for studying complex, natural and engineered systems. Novel network models of data arising
from internet analytics, systems biology, social networks, computational finance, and telecommunications have
led to many interesting insights. In this talk, we explore discrete optimization techniques for finding
cohesive data within these network-based models. The goal is to detect cohesiveness in spite of missing
information (linkages). In this regard, we will explore different aspects of cohesiveness and how they are
used for different applications. In particular, we will focus in on three particular structures: k-plex,
k-core, and k-club. All three are generalizations of the clique structure and were first utilized for social
network analysis. This talk is based on joint work with John Arellano, Baski Balasundaram, Sergiy Butenko,
Ben McClosky, and Foad Pajouh.
Hybrid optimization algorithms to solve real-world problems
Optimization algorithms are playing an increasingly important role in improving the operations of many standard corporate activities such as supply chain management, real-time scheduling and routing, and the pricing of goods and services through auctions. In this talk, we examine several large-scale real-world problems recently solved using hybrid optimization techniques.
First, we describe a high-profile government auction where the Federal Communications Commission (FCC) bought back spectrum from TV stations, packed the remaining broadcasters into a smaller swath of spectrum and sold the acquired spectrum to the wireless industry. Optimization was used before, during and after this auction to assure that multiple governmental goals are met. Our second example considers how the military can use similar optimization strategies to allocate limited spectrum during combat operations when spectrum is scarce and communication vital. In both examples, the underlying structure is that of a graph-coloring problem with multiple side constraints. Our approach is to use a combination of combinatorial optimization, heuristics, decompositions, and constraint programming to create an overall algorithm capable of solving to global or near global optimality problems with millions of variables and hundreds of thousands of constraints.
Our third example explores real-time routing and scheduling where one needs near-optimal solutions in less than a second. In this case, we compare and seek to determine the conditions under which the following algorithms provide the best overall performance: enumeration, constraint programming, heuristics, and global optimization techniques.
In each application, we use realistic data sets that we make available to the research community. We conclude with suggestions for other areas that seem ripe for exploitation by similar hybrid optimization approaches.
What Decision Diagrams Can Do for You
Decision diagrams have been used for decades as a compact representation of Boolean functions. More recently, they have emerged as a powerful tool for optimization. They provide a discrete relaxation of the problem that does not require linearity or convexity. The relaxation yields useful bounds and novel search strategies. This talk surveys recent applications of decision diagrams to discrete and nonlinear optimization, constraint programming, logic-based Benders decomposition, and comprehensive postoptimality analysis. Because a decision-diagram-based solver naturally accepts recursive dynamic programming (DP) models, it provides a new approach to solving DP problems by branch and bound rather than state space enumeration. In addition, use of a reduced decision diagram can sometimes lead to radical simplification of the state space.
Argonne National Lab
A Globally Convergent Cutting-Plane Method for Simulation-Based
Optimization with Integer Constraints
Many design and engineering applications result in optimization
problems that involve so-called
black-box functions as well as integer variables, resulting in
optimization problems (MIDFOs). MIDFOs are characterized by the fact
that a single function
evaluation is often computationally expensive (requiring a simulation
run for example) and
that derivatives of the problem functions cannot be computed or
In addition, many problems involve integer variables that are
non-relaxable, meaning that
we cannot evaluate the problem functions at non-integer points.
In the first part of our talk, we survey applications of MIDFO from a
range of Department
of Energy applications. The design of nano-photonic devices involves
variables due to manufacturing limitations, and each function
evaluation requires a
finite-element simulation that takes several hours to run on a
automatic performance tuning of code snippets for high-performance
non-relaxable integer variables such as loop-unroll-factors and
compiler options and
require several runs to eliminate random measurement errors. Finally,
the design and
operation of concentrating solar plants, requires forward simulations
that take hours
on a desktop and involve unrelaxable decision such as the number of
panels on the receiver.
In the second part of our talk, we present a new method for
non-relaxable MIDFO that enables us to prove
global convergence under idealistic convexity assumptions. To the best
of our knowledge this is the
first globally convergent method for non-relaxable MIDFO apart from
Our method constructs hyperplanes that interpolate the objective
function at previously evaluated points.
We show that in certain portions of the domain, these hyperplanes are
valid underestimators of the objective,
resulting in a set of conditional cuts. The union of these conditional
cuts provide a nonconvex
underestimator of the objective. We show that these nonconvex cuts can
be modeled as a standard
mixed-integer linear program (MILP). Unfortunately, this MILP model
turns out to be prohibitively
expensive to solve even with state-of-the-art MILP solvers. We develop
an alternative approach
that is computationally tractable, and provide some early numerical
experience with our new method.
Co-Authors: Prashant Palkar, Jeffrey Larson, and Stefan Wild