Skip to main content

About this book

In this book, theory of large scale optimization is introduced with case studies of real-world problems and applications of structured mathematical modeling. The large scale optimization methods are represented by various theories such as Benders’ decomposition, logic-based Benders’ decomposition, Lagrangian relaxation, Dantzig –Wolfe decomposition, multi-tree decomposition, Van Roy’ cross decomposition and parallel decomposition for mathematical programs such as mixed integer nonlinear programming and stochastic programming.

Case studies of large scale optimization in supply chain management, smart manufacturing, and Industry 4.0 are investigated with efficient implementation for real-time solutions. The features of case studies cover a wide range of fields including the Internet of things, advanced transportation systems, energy management, supply chain networks, service systems, operations management, risk management, and financial and sales management.

Instructors, graduate students, researchers, and practitioners, would benefit from this book finding the applicability of large scale optimization in asynchronous parallel optimization, real-time distributed network, and optimizing the knowledge-based expert system for convex and non-convex problems.

Table of Contents


Logic-Based Benders Decomposition for Large-Scale Optimization

Logic-based Benders decomposition (LBBD) is a substantial generalization of classical Benders decomposition that, in principle, allows the subproblem to be any optimization problem rather than specifically a linear or nonlinear programming problem. It is amenable to a wide variety of large-scale problems that decouple or otherwise simplify when certain decision variables are fixed. This chapter presents the basic theory of LBBD and explains how classical Benders decomposition is a special case. It also describes branch and check, a variant of LBBD that solves the master problem only once. It illustrates in detail how Benders cuts and subproblem relaxations can be developed for some planning and scheduling problems. It then describes the role of LBBD in three large-scale case studies. The chapter concludes with an extensive survey of the LBBD literature, organized by problem domain, to allow the reader to explore how Benders cuts have been developed for a wide range of applications.
John N. Hooker

Multi-Tree Decomposition Methods for Large-Scale Mixed Integer Nonlinear Optimization

Most industrial optimization problems are sparse and can be formulated as block-separable mixed-integer nonlinear programming (MINLP) problems, defined by linking low-dimensional sub-problems by (linear) coupling constraints. Decomposition methods solve a block-separable MINLP by alternately solving master problems and sub-problems. In practice, decomposition methods are sometimes the only possibility to compute high-quality solutions of large-scale optimization problems. However, efficient implementations may require expert knowledge and problem-specific features. Recently, there is renewed interest in making these methods accessible to general users by developing generic decomposition frameworks and modelling support. The focus of this chapter is on so-called multi-tree decomposition methods, which iteratively approximate the feasible area without using a single (global) branch-and-bound tree, i.e. branch-and-bound is only used for solving sub-problems. After an introduction, we describe first outer approximation (OA) decomposition methods, including the adaptive, multivariate partitioning (AMP) and the novel decomposition-based outer approximation (DECOA) algorithm . This is followed by a description of multi-tree methods using a reduced master problem for solving large-scale industrial optimization problems. The first method to be described applies parallel column generation (CG) and iterative fixing for solving nonconvex transport optimization problems with several hundred millions of variables and constraints. The second method is based on a novel approach combining CG and compact outer approximation. The last methodology to be discussed is the general Benders decomposition method for globally solving large nonconvex stochastic programs using a reduced mixed-integer programming (MIP) master problem.
Ivo Nowak, Pavlo Muts, Eligius M. T. Hendrix

Kantorovich–Rubinstein Distance Minimization: Application to Location Problems

The paper considers optimization algorithms for location planning, which specifies positions of facilities providing demanded services. Examples of facilities include hospitals, restaurants, ambulances, retail and grocery stores, schools, and fire stations. We reduced the initial problem to approximation of a discrete distribution with a large number of atoms by some other discrete distribution with a smaller number of atoms. The approximation is done by minimizing the Kantorovich–Rubinstein distance between distributions. Positions and probabilities of atoms of the approximating distribution are optimized. The algorithm solves a sequence of optimization problems reducing the distance between distributions. We conducted a case study using Portfolio Safeguard (PSG) optimization package in MATLAB environment.
Viktor Kuzmenko, Stan Uryasev

Dynamic Energy Management

We present a unified method, based on convex optimization, for managing the power produced and consumed by a network of devices over time. We start with the simple setting of optimizing power flows in a static network, and then proceed to the case of optimizing dynamic power flows, i.e., power flows that change with time over a horizon. We leverage this to develop a real-time control strategy, model predictive control, which at each time step solves a dynamic power flow optimization problem, using forecasts of future quantities such as demands, capacities, or prices, to choose the current power flow values. Finally, we consider a useful extension of model predictive control that explicitly accounts for uncertainty in the forecasts. We mirror our framework with an object-oriented software implementation, an open-source Python library for planning and controlling power flows at any scale. We demonstrate our method with various examples. Appendices give more detail about the package, and describe some basic but very effective methods for constructing forecasts from historical data.
Nicholas Moehle, Enzo Busseti, Stephen Boyd, Matt Wytock

An Embarrassingly Parallel Method for Large-Scale Stochastic Programs

Stochastic programming offers a flexible modeling framework for optimal decision-making problems under uncertainty. Most practical stochastic programming instances, however, quickly grow too large to solve on a single computer, especially due to memory limitations. This chapter reviews recent developments in solving large-scale stochastic programs, possibly with multiple stages and mixed-integer decision variables, and focuses on a scenario decomposition-based bounding method, which is broadly applicable as it does not rely on special problem structure and stands out as a natural candidate for implementation in a distributed fashion. In addition to discussing the method theoretically, this chapter examines issues related to a distributed implementation of the method on a modern computing grid. Using large-scale instances from the literature, this chapter demonstrates the potential of the method in obtaining high quality solutions to very large-scale stochastic programming instances within a reasonable time frame.
Burhaneddin Sandıkçı, Osman Y. Özaltın

An Outer Approximation Algorithm for Capacitated Disassembly Scheduling Problem with Parts Commonality and Random Demand

Disassembly scheduling has attained increasing attention in the academic community of reverse logistics. This paper studies a capacitated multi-item multi-period disassembly scheduling problem with parts commonality and random demand. The problem is formulated as a mixed integer nonlinear program (MINLP) with chance constraints. The objective function of the model is to minimize expected total cost, including set-up cost, start-up cost, procurement cost, and expected holding inventory cost. A chance constraint is considered to probabilistically ensure the satisfaction of random demand. Based on the convexity of the proposed model, an outer approximation (OA) algorithm is developed to obtain optimal solutions. Closed-form formulations and numerical experiments are conducted when the demand follows normal distribution. Computational results reflect that the proposed OA algorithm significantly outperforms Bonmin, which is a well-known MINLP solver. Sensitivity analysis reveals practical managerial insights associated with the service level, production capacity, start-up cost, ratio of commonality, and demand deviation. And, a case from a valve maker is presented to demonstrate the application of the research in practice. Finally, conclusions are drawn and future research directions are discussed.
Kanglin Liu, Meng Wang, Zhi-Hai Zhang

An Approximation-Based Approach for Chance-Constrained Vehicle Routing and Air Traffic Control Problems

We proposed a polynomial approximation-based approach to solve a specific type of chance-constrained optimization problem that can be equivalently transformed into a convex program. This type of chance-constrained optimization is in great needs of many applications, and most solution techniques are problem-specific. Our essential contribution is to provide an all-purpose solution approach through Monte Carlo and establish the linkage between our obtained optimal solution with the true optimal solution. Thanks to fast-advancing computer hardware, our method would be increasingly appealing to businesses, including small businesses. We present the numerical results including the air traffic flow management (ATFM) and the capacitated routing problem (CVRP) with stochastic demand to show that our approach with Monte Carlo will yield high-quality, timely, and stable solutions. We apply the approach to the ATFM problem to efficiently solve the weather-affected traffic flow management problem. Since there are massive independent approximation processes in the polynomial approximation-based approach, a distributed computing framework is designed to carry out the computation. For the CVRP problem, we conclude that our chance-constrained method has some strategic advantages to serve a logistics company well when resource costs and service guarantees are of concern.
Lijian Chen

The Vector Optimization Method for Solving Integer Linear Programming Problems: Application for the Unit Commitment Problem in Electrical Power Production

Nowadays information technology is continuously implemented in all fields of industry, including power generation. One of the most important tasks of modern energy systems is reliable, effective, and safe planning of their work. The task of planning is also vital for single power plants. The solution of this task must satisfy requirements of financial effectiveness and conditions of energy system. This chapter deals with the solution of the problem of integer linear programming. For this purpose the author consistently represents the statement of the problem, the objective function, and the system of constraints that must be considered. To solve considered problem, the vector optimization method (VOM) is proposed. To illustrate the performance of the proposed method, the author provided the example of how to solve the unit commitment problem for the power station, in order to reach a maximum total financial profit. As a result of planning, the desired optimal sequence of combinations of operating turbogenerators is determined. To assess effectiveness of the VOM, the chapter provides an estimate of its computational cost in comparison with the computational cost of the dynamic programming method. The comparison results demonstrate the advantages of the VOM.
Lenar Nizamov

Algorithmic Mechanism Design for Collaboration in Large-Scale Transportation Networks

The importance of collaborative logistics is getting widely recognized in recent years. However, strategic revealing of private information and disagreements on how savings are split would make any efforts of collaboration unsuccessful. The large-scale nature of real-life transportation networks further complicates the implementation of collaboration, as the associated optimization problems are usually NP-hard. The academic community has developed a variety of methodologies by using operations research tools and algorithmic mechanism design to resolve these issues. We summarize the state-of-the-art progress in the literature and introduce the iterative mechanism design theories. The iterative mechanism design models consider private information and propose decentralized approximation algorithms to achieve a system-wide objective while eliciting truthful information through the iterations. Hence, iterative mechanism design effectively reduces computational and communication difficulties. We then apply the methodology to a truckload pickup-and-delivery collaboration problem as an example. Numerical results on large-scale instances are reported, verifying the effectiveness of the methodologies.
Minghui Lai, Xiaoqiang Cai
Additional information

Premium Partner

    Image Credits