Hello, I'm Rob Pratt.
I'm Senior R&D Manager at SAS.
In this video, I'll show you how to use
PROC OPTMODEL to solve optimization problems
with hybrid approaches.
PROC OPTMODEL contains an algebraic modeling language
that enables you to define optimization problems
by declaring decision variables, constraints, bounds,
and objectives algebraically.
It also supports numeric or character parameters, arrays,
and index sets.
As a SAS procedure, OPTMODEL is closely integrated with the SAS
programming environment.
You can read and write as many data sets as you want.
As with any modeling language, it
supports separation between model and data
so that you can solve other instances
just by changing the data and not changing the model.
PROC OPTMODEL is interactive and provides direct access
to the linear, mixed integer linear, quadratic, nonlinear,
constraint programming, and network solvers.
As I'll illustrate, you can write customized algorithms.
PROC OPTMODEL includes almost all
of the standard SAS functions.
And you can also write your own functions by using PROC FCMP.
For simple enough optimization problems,
you can formulate a model, call the appropriate solver,
and report the resulting solution.
But for some problems, the best approach
is to combine the strengths of several solvers
by writing a customized algorithm that invokes
the solver as subroutines.
The first example is the p-median problem,
which is a type of facility location problem
that I'll describe in more detail in later slides.
It uses both the mixed integer linear and linear programming
solvers.
The second example is a political distracting problem
that uses MILP constraint programming and two algorithms
from the network solver--
connected components and shortest path.
The third example is an oil well scheduling and routing
problem that uses the MILP and network solvers again
to compute connected components, but also to solve
several traveling salesman problems that arise.
The p-median problem is a variant
of the uncapacitated facility location problem.
The inputs are the customer locations, weights--
which might represent importance or amount of demand--
and a positive integer, p.
The problem is to select exactly p of the customer locations
to build facilities.
And the objective is to minimize the total weighted distance
from each customer to that customer's closest facility.
This plot shows the customer locations for 200 customers.
If p equals 5 and all weights are 1,
the resulting optimal solution looks
like this with five locations selected as facilities.
Each edge joins a customer to the closest facility.
Here's the first snippet of PROC OPTMODEL code.
The first var statement declares a binary decision variable,
Build j, that indicates whether to build a facility at site j.
The second var statement declares
a non-negative decision variable, Assign ij,
that represents the proportion of customer
i's demand to assign to a facility at site j.
The Min statement declares the objective
to minimize total weighted distance, which
is a linear function of the assigned variables.
The first Con statement declares a cardinality constraint
that forces exactly p facilities to be built.
The Assign Once constraint assigns each customer
to exactly one site.
And the final constraint uses a linear inequality
to enforce the logical implication
that if a customer i is assigned to site j,
then a facility must be built at j.
The solve statement then invokes the MILP solver.
This direct approach to solve the problem
can require a large amount of memory and computational time
for a large number of customers.
Next, I'll describe an indirect approach
that uses an optimization method called Benders decomposition.
This method applies to problems for which
fixing a set of complicating variables
makes the resulting problem easy.
In the original paper by Benders in 1962
in which he considered MILP problems,
he recommended taking the integer variables
as complicating, because fixing all the integer variables
leaves a linear programming problem over the remaining
continuous variables.
And this LP is much easier than the original MILP.
Benders decomposition involves a MILP master problem
that recommends values for the complicating
variables and an LP suproblem that
generates optimality and feasibility cuts for the master
problem.
The algorithm iterates between master and subproblem
until the optimality gap is small enough.
Benders decomposition is a dual of Dantzig-Wolfe decomposition,
which involves complicated constraints,
rather than complicating variables.
The PROC OPTMODEL code showed here defines the MILP master
problem.
There is a new non-negative variable called Eta.
And the objective is to minimize Eta.
For the p-median problem, the subproblem is always feasible.
So the master problem does not include any feasibility cuts.
But it does include optimality cuts, which
are generated dynamically.
Initially, the numeric parameter num_optcuts is zero.
And so the set OPTCUTS is empty.
The optimality cut constraints are declared only once
and are automatically updated when num_optcuts changes.
The problem statement declares a problem
called Master that contains the build
variables and cardinality constraint
declared earlier, as well as the Eta variable, master
objective, and optimality cuts declared in this slide.
The LP Subproblem is even simpler.
It is the same as the original MILP,
except that the complicating build variables are fixed.
The problem statement declares a problem called Subproblem
that includes everything from the original problem
except the build variables and the cardinality constraint that
involves only the build variables.
This do until loop is the heart of the Benders decomposition
implementation.
The use problem statement in line two
switches focus to the master problem.
And the solve statement in line three invokes the MILP solver.
Lines four through seven record some information
about the resulting solution.
The use problem statement in line eight
switches focus to the subproblem.
And the solve statement in line nine invokes the LP solver.
If the resulting feasible solution
is better than the incumbent solution,
the best_upper_bound and incumbent are updated.
If the master objective has underestimated
the true objective, the subproblem dual values
are used to generate a new optimality cut for the master.
This back and forth between MILP master LP Subproblem
continues until the optimality gap
between lower and upper bound decreases to some user
specified threshold.
Although this approach is more complicated
than just calling the MILP solver once,
Benders decomposition exploits problem structure
and can reduce the amount of memory
needed to solve large problems.
For more details, including all of the code needed
to solve another facilty location variant,
see the SAS Global Forum 2011 paper listed here.
The other two papers cover the political districting problem
and oil well scheduling and routing
problem mentioned earlier.
All three examples illustrate the use
of multiple solvers within one PROC OPTMODEL session
to implement a customized algorithm.
This concludes the video.
I hope you find these examples useful
when you encounter difficult optimization problems.
For more information, please visit support.sas.com