A note from Udo Sglavo: This post offers an introduction to complex optimization problems and the sophisticated algorithms SAS provides to solve them. In previous posts of this series, we learned that data availability, combined with more and cheaper computing power, creates an essential opportunity for decision-makers. After looking at network analytics specifically, we now want to discuss yet another ingredient of the digitalization transformation journey: how can we automate decisions at scale in an optimal fashion? Questions that might keep us from our peace of mind include:

• Is what we're trying to accomplish possible?
• What's the best we can do?
• What happens if conditions change?

So how can we do better? In this post, Rob Pratt, Senior Manager in Scientific Computing R&D, provides us with a whirlwind tour of the many facets of SAS Optimization.

Decisions, decisions, decisions!

You make decisions every day: what time to get up, what to wear, what to eat, what route to drive to work (well, not so much lately), when to schedule a meeting, which check-out line to join, and so on. Often, you make these decisions with little thought, based on instinct or what you did the last time you faced a similar situation. If the reasonable options are few and the consequences of the decisions do not vary widely, then it doesn’t really matter much what choice you make.

But if the differences in outcomes are significant and the options are numerous, especially if multiple decisions are interdependent, you have a good opportunity to apply analytics.

Mathematical optimization is one of the most valuable disciplines in analytics, with applications in every industry. It is used to rigorously search for the best way to use resources to maximize or minimize some metric while respecting business rules that must be satisfied.

Easy to describe, difficult to solve? Examples of SAS Optimization success

Often, optimization is applied to business problems that are easily described but difficult to solve. Let’s review some examples that meet that description. Each of these problems was solved using the advanced features of SAS Optimization, and many were implemented by the SAS Analytics Center of Excellence.

How can you safely meet oil well service levels with lower costs for the company and better hours for technicians? 
Using SAS/OR® to Optimize Scheduling and Routing of Service Vehicles describes the use of the mixed integer linear programming (MILP) solver and the network solver to assign service technicians to oil wells in a way that minimizes travel costs while satisfying service frequency requirements and respecting limits on working hours per day.

How can you divide a geographic region into equal zones?
Using the OPTMODEL Procedure in SAS/OR® to Solve Complex Problems explains how to use the MILP, constraint programming, and network optimization solvers to solve a political districting problem that partitions a geographic region into a specified number of smaller contiguous subregions in a way that minimizes the differences in populations between regions.

How can you help more sports fans return to the stadium while maintaining social distancing guidelines?
Why Venue Optimization is Critical and How It Works, by Sertalp Cay, discusses a COVID-19 project that uses our optimization solvers to determine which stadium seats to sell in order to maximize revenue while respecting social distancing guidelines.  This post also mentions a fun seating optimization game that challenges you to find an optimal seating arrangement and then compares your choices against what the MILP solver finds.

How can you improve production levels while meeting all quality requirements in manufacturing?
One project for a large manufacturer and distributor of pulp, paper, and building products develops an analytical flow process to support scoring of the predictive models, optimization, and visualization of the wallboard manufacturing process. In the optimization phase, the objective is to maximize yield such that the constraints meet business rules and keep key performance indicators (for quality and waste measures) within their expected ranges. Then the optimization output provides recommendations for controllable settings for the wallboard manufacturing process. The mathematical formulation of this project is a nonlinear optimization problem that is formulated and solved by using SAS Optimization.

How can you produce the best laundry detergent at the lowest cost?
A laundry portfolio optimization project for Procter & Gamble sets portfolio strategy for a multi-billion-dollar laundry business. The mathematical formulation of this project is a mixed integer nonlinear optimization problem. The objective is to minimize the total cost of the recommended ingredient levels while meeting quality constraints and business rules. The solution approach uses a COFOR loop to solve multiple independent nonlinear programming (NLP) subproblems concurrently and then uses the resulting solutions as input to the MILP solver.  Earlier work related to this ongoing project led to a joint team from Procter & Gamble and SAS being named by INFORMS as finalists for the 2014 Daniel H. Wagner Prize for Excellence in Operations Research Practice.

How can you prevent power outages by reducing contact between electric lines and trees?
Another project for Honeywell concerns tree contact with transmission lines, a leading cause of electric power outages and a common cause of past regional blackouts. The objective of the model is to minimize the risk of failure of a power circuit, which is defined by user-provided metrics, information regarding priority of the network, population affected if the network experiences an outage, the cost of bringing a system back up after failure, and so on. Using estimated tree growth projections, the idea is to provide a schedule of when a circuit should be serviced and by which vendor. It is a simple assignment problem that ensures that the recommended schedule cost does not exceed the predefined budget. The problem is solved by using the MILP solver in the runOptmodel action.

How can you improve the bussing experience for students with disabilities?
For Boston Public Schools, an important problem is to optimally assign monitors or supervisors to accompany students with disabilities on school buses. Several rules need to be respected in assigning monitors to students, with a goal of maximizing the number of routes within each monitor’s package.  The solution approach uses the network solver to enumerate paths, the MILP solver to solve an integer multicommodity flow problem, and the network solver to decompose the resulting solution into directed cycles.  More details are available in this SAS Global Forum 2020 poster

How you can solve more optimization problems with SAS

These projects exemplify how the era of big data and big computing power has made it possible to construct larger and more detailed optimization models that capture both the relationships among decision variables and their contributions to the metric being optimized. To solve these increasingly complex problems, sometimes even a set of models is needed where the output of one model becomes the input for a subsequent model. As optimization becomes one step of many in the modeling processes, data scientists and other modelers expect to solve these problems using their favorite language as part of an integrated workflow.

SAS® Optimization in SAS® Viya includes several distinguishing features that support these needs.  In addition to traditional mathematical optimization solvers for linear programming (LP), mixed integer linear programming (MILP), quadratic programming (QP), and nonlinear programming (NLP), SAS Optimization includes constraint programming, black-box optimization, and network optimization. All of these are accessible from the same algebraic modeling language, OPTMODEL.

Like the rest of SAS Viya, optimization actions make the various solvers available from SAS, Java, Lua, Python, R, and REST APIs. For many years, OPTMODEL has supported a Coroutine FOR (COFOR) loop to solve independent problems concurrently, either on a single machine or in distributed mode.  By design, the syntax is minimal, in many cases requiring only a single keyword change from FOR to COFOR.

For the NLP solver, the multistart feature increases the likelihood of finding a globally optimal solution for highly nonconvex problems that have many local optima.  This feature is available in both single-machine and distributed modes. The runOptmodel action now supports BY-group processing for the common use case of building and solving the same problem multiple times with different input data.  This functionality does not require any explicit looping, and both problem generation and solver execution are automatically parallelized.

The network solver contains a large suite of algorithms, many of which are threaded and distributed. It also supports generic BY-group processing. The newest algorithm added solves the capacitated vehicle routing problem. The latest release contains automated linearization techniques that introduce new variables and constraints to transform several common nonlinear structures to linear form.  This improvement enables you to make broader use of the fast linear optimization solvers in SAS Optimization without needing to explicitly modify your models to use only linear functions.

For the MILP solver, the default branch-and-cut algorithm threads the dynamic tree search.  In distributed mode, the solver processes tree nodes on different workers and communicates new global lower and upper bounds back to the controller. The LP and MILP solvers both include a threaded and distributed Dantzig-Wolfe decomposition algorithm that exploits block-angular structure in the constraint matrix. For MILP problems that consist of loosely coupled subproblems, this algorithm often yields dramatic performance improvements over branch-and-cut.

More optimization resources

I hope this blog post has helped you learn about some applications of mathematical optimization and how you can use SAS software to solve optimization problems.  We continue to add new features that make it easier for users to model complex optimization problems, and in every release, we make performance improvements to solve those problems more quickly. For more information:

• The SAS Optimization documentation is the definitive source of information for the procedures and actions in SAS Optimization. SAS/OR® 15.2 User's Guide: Mathematical Programming Examples includes 29 examples that illustrate various features and demonstrate best practices.
• The Mathematical Optimization, Discrete-Event Simulation, and OR SAS Support Community provides assistance for SAS/OR, SAS Optimization, and SAS Simulation Studio.
• The Operations Research SAS blog explores the use of operations research modeling methods and solution algorithms in optimization, simulation, scheduling, and related areas.
• The SAS Software Statistics and Operations Research YouTube channel includes over one hundred short videos.

LEARN MORE | SAS Optimization

This is the seventh post in our series about statistics and analytics bringing peace of mind during the pandemic.