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.

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 Orlando Rivera.

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.

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.

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.

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.

Many design and engineering applications result in optimization problems that involve so-called black-box functions as well as integer variables, resulting in mixed-integer derivative-free 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 estimated efficiently. 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 integer decision variables due to manufacturing limitations, and each function evaluation requires a finite-element simulation that takes several hours to run on a cluster. Similarly, automatic performance tuning of code snippets for high-performance computing involves 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 complete enumeration. 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

When an exact mixed-integer programming formulation resists attempts at solution, sometimes much better results can be achieved by "cheating" a bit on the formulation. Typically, a judicious choice of reformulation, restriction, or decomposition serves to make the problem easier, in a way not guaranteed to preserve the solution's optimality but highly unlikely to make much of a difference given the model and data of interest. This tutorial illustrates such an approach through a series of case studies. All rely on trial and error, a flexible modeling language, and a good general-purpose solver, and each is seen to be founded on one or two simple ideas that have the potential to be more broadly applied.

MILP solvers have been improving for more than 40 years, and performance tuning tactics regarding both adjusting solver strategies and model formulations have evolved as well. State-of-the-art global nonconvex MIQP solvers have improved dramatically in recent years, but they lack the benefit of 40 years of evolution. Also, they use a broader notion of branching that can create different performance challenges. This talk will assess the effectiveness of existing MILP tuning tactics for solving nonconvex MIQPs, as well as consider more specific strategies for spatial branching. It will also examine in detail some tightening strategies specific to nonconvex MIQPs involving bilinear terms of binary variables and their associated linearizations.

Stochastic optimization is a fragmented field that spans topics such as stochastic programming, Markov decision processes, reinforcement learning, bandit problems and stochastic search, featuring different modeling styles and notational systems, and competing solution strategies.
I will give a common mathematical framework for modeling all of these problems, illustrated using a range of applications. This framework consists of five fundamental elements, and requires optimizing over policies, which is the major point of departure. I will identify four (meta)classes of policies which will work, in some combination, over all problems. I will then highlight the role of offline vs. online learning, and state-independent vs. state-dependent problems.