Slide 75 

1 Integration of Artificial Intelligence and Operations Research Techniques for Combinatorial Problems Carla P. Gomes Cornell University gomes@cs.cornell.edu Ken McAloon and Carol Tretkoff ILOG {mcaloon,tretkoff}@ilog.com 2 AI, OR, and CS AI OR CS 3 Integration of Artificial Intelligence & Operations Research Techniques AI Representations
Constraint Languages
Logic Formalisms
ObjectOriented Prog.
Bayesian Nets
Rule Based Systems
• • •
Tools
Constraint Propagation
Systematic Search
Stochastic Search
• • •
Pros / Cons
Rich Representations
Computational Complexity OR Representations
Mathematical
Modeling Languages
Linear & Nonlinear
(In)Equalities
• • •
Tools
Linear Programming
MixedInteger Prog.
Nonlinear Models
• • •
Pros / Cons
More Tractable (LP)
Primarily Complete Info
Limited Representations Combinatorial Problems Planning Scheduling THE CHALLENGE
AI OR
UNIFY APPROACHES TO: SCALE UP SOLUTIONS
HANDLE UNCERTAINTY
ANALYZE COMPLEXITY (phase transition) EXPLOIT PROBLEM STRUCTURE
INCREASE ROBUSTNESS 4 Outline
I. Short Overview of OR
II. Disjunctive Programming and Hybrid Solvers
III. Exploiting Randomization to Solve Hard Combinatorial Problems
IV. Conclusions 5 I. Short OR Overview 6 Outline for Linear Programming and Integer Programming
Standard Form of LP and a Simple Example
Geometric Interpretation of LP
Complexity issues
MIP
Example: Fast Food
Example: Capacitated Warehouse
Example: 911
7 Outline
1. Short Overview of OR
2. Constraint Programming
3. Cooperating Solvers
4. Disjunctive Programming
5. Exploiting Randomization to Solve Hard Combinatorial Problems
6. Conclusions 8 Optimization Technology Evolution Dispatch
Rules 1960 1970 1980 1990 SA, GA, Tabu CPM
PERT Constraintbased Scheduling 1998 1947 Primal Simplex LP Parallel
LP/MIP Concurrent
Scheduling Interior Point Constraint
Propagation Large IPs MIP Shifting
Bottleneck First CP Systems Cooperating
Solvers (LP/CP) Global constraints Barrier LP Barrier Crossover Dual Simplex Implementation Dual Simplex 9 1. Short OR Overview 10 Outline for Linear Programming and Integer Programming
Standard Form of LP and a Simple Example
Geometric Interpretation of LP
Complexity issues
MIP
Example: Fast Food
Example: Capacitated Warehouse
Example: 911
11 An LP Story A factory can produce n products from m parts
For product j it needs aij units of part i
There are bi units of part i available
Each unit of product j sold earns cj
Amount of each product to make is unknown xj 0
Each part i determines a constraint
ai1 x1 + … + ain xn bi
Obvious solution: do nothing
Better: maximize c1 x1 + … + cn xn
12 Standard Forms of LP A linear program (LP) in standard form (Dantzig 1947)
max cTx
subject to Ax b
x 0
Input data: c (n x 1), A (m x n), b (m x 1).
Variables: x (n x 1)
13 Standard Forms of LP // The objective function
max c1 x1 + … + cn xn
// The constraints
subject to
a11 x1 + … + a1n xn b1
...
am1 x1 + … + amn xn bm
x1 0 , … , xn 0 14 Standard Forms of LP
In OR emphasis is on optimality
Solution means optimal solution
Feasible solution means solution in the ordinary sense 15 Standard Forms of LP Interpretation of standard form:
xj = amount of product j to make
cj = revenue per unit product j
bi = available amount of component i
aij = units of i used per unit of j produced
The constraints “say”:
aijxj = units of i used by j
= units of i used
bi
16 What are models? A model is a dataindependent abstraction of a problem
A model lets you write down the mathematical representation of a model independently of the data
Project Model Data One
Problem
Instance 17 Products Could be Jewelry Products: Rings and Earrings
Components: Gold and Diamonds
One ring requires 3 units of Gold, and 1 Diamond
One set of earrings requires 2 units of Gold, and 2 Diamonds
Total Gold and Diamonds are limited
Profit is different for Rings than for Earrings Products = { rings, earrings };
Components = { Gold, Diamonds };
demand = [ [3, 1], [2, 2] ];
stock = [150, 180];
profit = [60, 40];
18 Products: Ammonium Gas = NH3 Ammonium Chloride = NH4Cl
Components: Nitrogen, Hydrogen, Chlorine
One unit of Gas requires 1 unit of Nitrogen, 3 units Hydrogen
One unit of Chloride requires 1 unit of Nitrogen, 4 units Hydrogen, and 1 unit of Chlorine
Total Nitrogen, Hydrogen, Chlorine is limited
Profit is different for Gas than Chloride Products Could be Chemicals Products = { gas, chloride };
Components = { nitrogen, hydrogen, chlorine };
demand = [ [1, 3, 0], [1, 4, 1] ];
stock = [50, 180, 40];
profit = [30, 40]; 19 The Problems Have One Model enum Products ...;
enum Components ...;
float+ demand[Products, Components] = ...;
float+ profit[Products] = ...;
float+ stock[Components] = ...;
var float+ production[Products];
maximize
sum (p in Products) profit[p] * production[p]
subject to {
forall (c in Components)
sum (p in Products)
demand[p, c] * production[p]
<= stock[c]
}; 20 OR Modeling Systems
OPL
AMPL
2LP
AIMMS
GAMS
MPL
ILOG Planner
etc
21 The Dual The dual linear program (von Neumann 1947);
min yTb
subject to yTA c
y 0
Variables y (m x 1)
Awesome Symmetry 
The dual of the dual is the primal
22 Rows and Columns Exchanged
min b1 y1 + … + bm yn
subject to
a11 y1 + … + am1 ym c1
...
a1n y1 + … + amn ym cn
y1 0 , … , ym 0 23 Duality Theorem Theorem: min yTb = max cTx
Consequence: This turns optimality problem into a feasibility problem in x and y
Ax b
x 0
yTA cT
y 0
yTb = cTx
Consequence: Enumeration not needed to verify optimality
24 Duality Theorem
Sensitivity Analysis
Consequence: The solution values y* for the y variables yield the Lagrange multipliers of the primal constraints which measure the rate of change of the objective function with respect to the right hand side bounds b
yi * = Z / bi where Z is the optimum
Reference: McAloon and Tretkoff [1996] Wiley Duality Two different views of the same phenomenon Point vs Set Arc vs Node Momentum vs Position Vector vs Hyperplane Landlord vs Renter 26 Simplex and Barrier
The simplex algorithm turns the feasibility problem into a iterative repair process with a powerful evaluation function
The barrier method transforms the LP into a system of differential equations that describe a vector field of flow on the polytope 27 Geometric Interpretation of LP
X Y Max: X
subject to:
X + Y <= 4
X + 4*y <= 36
2*X + y <= 23
X + Y >= 4
Y >= X + 10 (0,4) (4,0) (8,0) (10,3) (4,8) Barrier Simplex 28 Complexity of Linear Programming Simplex Method
Worstcase  exponential (Klee and Minty 72)
Practice  good performance
Ellipsoid Method
Khachian’s Ellipsoid Method
Worstcase  polynomial
Practice  poor performance
29 Complexity of Linear Programming Interior Point Methods or Barrier Methods
“Karmarkar’s” (and variants) Method
Worstcase  polynomial
Practice  good performance
30 Complexity of Linear Programming
Despite its worst case exponential time complexity, the simplex method is usually the method of choice since it provides tools for sensitivity analysis and its performance is very competitive in practice.
Which method performs best is problem dependent. 31 Success Stories Industrial Planning
Given current resources, decide what to produce in what quantity
Supply Chain Management
Multiperiod planning models that link flow from one period to the next
Network Flow
How best to route goods across a network 32 Assumptions of Linear Programming
Linearity
when violated: ( xy = 50)
Nonlinear programming
Continuity
when violated: (x integral)
(Mixed) Integer programming
33 Assumptions of Linear Programming  continued
No Disjunctive Constraints
when violated: (x 100 or x 0)
Disjunctive programming
Additional 01 variables and Big M constraints
Certainty
when violated: (cost c is a random variable)
Stochastic programming
34 Search and MIP
In order to deal with variables that must have integer values in the solution, a search must be performed.
Mixed Integer Programming problems are combinatorial optimization problems and are NP hard
feasibility is NPComplete
verifying optimality is coNPComplete
35 MIP and Combinatorial Optimization
These problems have been attacked by both the AI and OR communities.
In AI, these problems are attacked as CSPs or as Planning Problems.
In OR, they are done as MIPs and use linear relaxation to help guide the search.
The overriding idea in each case is to limit search.
36 Integer Program: All Integer Points in Region 37 Cut to Create Integer Vertex Integer Vertex 38 Example  Fast Food
Question: Is it possible for a male college student to eat at the local fast food outlet and still meet the requirements of a balanced diet?
If so, what is the least he can do it for? 39 Nutritional Requirements
At least 100% of vitamins A, C, B1, B2, niacin, calcium and iron
At least 55 grams of protein
At most 3000 milligrams of sodium
At most 30% of the calories can come from fat
Nutritional information is available from fast food outlets 40 College Student’s Requirements
At least 2000 calories a day
No more than 3 servings of any one food
Milk only with cereal and not as a standalone drink 41 Fast Food  MIP Model
We will have variables Servk to represent the number of servings of item k in the plan.
The variable Servk will have to take an integer value for the solution to be valid.
The objective function: Z for cost 42 Fast Food  MIP Model
Let foodk,j represent the percent of RDA of nutrient j in a serving of item k
The for each nutrient j, we have a constraint
foodk,j Servk 100
k
43 Fast Food  MIP Model
Let sodiumk represent the amount of salt in a serving of item k
For salt we have the constraint
sodiumk Servk 3000
k
Similarly for fat
44 Fast Food  MIP Model
Let costk represent the cost of a serving of item k
For the objective function we have the defining constraint
costk Servk = Z
k
45 Fast Food  Solution
With a MIP solver and a way to input these constraints we ask for
a solution that makes the variables Servk integral
and which minimizes Z 46 MIP Solution Technique
What the MIP solver does is to carry out a branch and bound search guided by
the linear relaxation
the solution to the problem with the integrality requirements relaxed
Initialize the global variable best_so_far to 1000 (or something else very big).
47 At a Node
Compute a solution to the linear relaxation which minimizes Z yielding z*. Prune this node if
z* best_so_far ,
If all values of Servk are integral, this is a solution. Set best_so_far = z*. Save this node.
48 Branching at a node
Choose a variable Servk whose value s* is not integral.
Typical heuristic: most nonintegral variable
Create two child nodes,
add Servk floor(s*)
add Servk ceil(s*)
49 Good News
The linear relaxation can prune nodes before all variables Servk are forced to be integral.
Surprisingly often a node “high in the tree” will turn up with all relevant variables integer. Here’s why
A solution to the LP is at a vertex
A vertex is defined as the simultaneous solution of the equality form of n linearly independent constraints
Many of these constraints are integer bounding constraints yielding X = integer
50 Arboreally Speaking
Breadth first search is often preferred  it visits the “smallest” number of nodes needed to find and verify the optimal solution  analogous to A*
If the linear relaxation is tight
 z*linear  z*integral  is relatively small
then z*linear is an excellent evaluation function 51 Answer  Fast Food
Total cost is 8.71
Buy 3 burgers
Buy 2 fries
Buy 3 honeys
Buy 1 yogurt
... 52 Example  Fixed Cost
Warehouses must be rented in order to supply stores and we must decide which to use
For each store j we know its monthly demand dj
For each warehouse i we know its capacity ki
For each warehouse i we know the fixed cost to run it each month fci
For each pair i, j we know the monthly cost cij of supplying j from i 53 Example  Fixed Cost
Xij is the fraction of store j’s demand met by i
Xij 1
Yi is a “fuzzy” boolean
it will be 1 if the warehouse is rented
0 if it is not rented
Yi 1 54 Example  Fixed Cost
Each store must be supplied
X ij = 1
i
Warehouse capacity can not be exceeded
dj Xij ki
j
Tighter
dj Xij ki Yi
j 55 Example  Fixed Cost
Objective function
fci Yi + cij Xij
This yields a MIP with 01 variables Yi
56 Branch and Cut: An Enhanced Solution Method
Cuts  redundant constraints for the MIP model but not redundant for the linear relaxation
Xij Yi
Add at a node if violated by solution to linear relaxation
Powerful method  will solve the Imperial College OR lib CW problems very easily 57 Example  Call 911
PCTs answer the phone 24 hours a day, 7 days a week.
It is known how many PCTs should be on duty during each of the 168 hours during the week in order to assure the necessary response rate.
Workers can arrive at any hour and they work for 8 hours except for a one hour break after 4 hours. 58 Example  Call 911 Each PCT has a work week of 5 days followed by 2 days off.
Want to meet the demand with minimal or nearminimal number of PCTs.
So need to determine how many PCTs start their work week at each hour h of the week
59 Modeling 911
A continuous variable Pcth will represent the number of workers who start their work week at hour h, 0 h < 168.
60 Modeling 911
A continuous variable Z will represent the objective function
Pcth = Z
h
There will be a constraint for each hour h to assert that there are enough workers on duty at that time. The rhs of this constraint is bh = the number of workers needed.
61 Modeling 911
For this constraint we need to represent the number of workers who are on duty at time h
Certainly, those who start the week at time h are here, as are those who started the week at time h  1
And so on back to time h  7 with the exception of those who started at time h  4 and who are now on break.
62 Modeling 911
This also applies to the previous 4 days. When the smoke clears, we sum over the workers w who are working at time h
Pctw bh
w
63 Call 911 solved with progressive roundoff int b[168] = { // New York City 911
30,24,18,15,14,14,15,25,34,36,38,40,
41,43,46,57,57,59,61,59,55,50,45,38,
32,25,20,17,15,13,17,25,32,35,38,40,
42,43,47,58,57,57,59,57,55,52,47,41,
33,25,20,17,15,13,15,25,32,33,37,39,
42,43,47,57,56,57,57,56,53,50,47,41,
34,27,22,19,16,15,16,25,31,35,37,40,
44,45,48,57,57,56,58,56,53,53,46,41,
34,28,23,19,16,15,17,25,33,37,39,42,
45,47,51,59,58,60,61,61,57,56,57,55,
48,41,35,30,26,20,18,22,26,32,42,46,
49,53,54,56,56,56,59,59,57,57,56,56,
52,46,41,34,29,23,18,19,25,31,36,41,
46,50,52,53,52,53,54,53,50,49,45,40
}; 64 Modeling 911
Subject to these constraint we want to find a solution which makes the Pcth integer and which makes Z small.
The naïve approach is to compute the minimal linear solution and to round up all the values of Pcth to the nearest integer.
The linear relaxation yields Z = 204.67 “fuzzy workers” but rounding yields a mediocre integral solution of 259 workers.
65 Modeling 911
For this and many other applications, heuristics can be used to develop good solutions
Progressive Roundoff  solve the linear relaxation, round up first variable and freeze it, resolve etc.
66 Solving the Integer Problem main() // Planner Code
{
IlcInitFloat();
IlcManager m(IlcNoEdit);
IlcLinOpt simplex(m);
IlcFloatVarArray Pct(m,168,0,1000);
IlcFloatArray coeffs(m,168);
int i,j,k,h,n; 67 Solving the Integer Problem
// Pctw bh
w
for(h=0;h<168;h++) { // for each hour of 168 in week
for(j=0;j<168;j++)
coeffs[j] = 0;
for(k=0;k<5;k++) // for each of 5 days
for(j=k*24;j= b[h]);
}
68 Solving the Integer Linear Problem
IlcFloatVar Z = IlcSum(Pct);// Objective
simplex.setObjMin(Z);
for(i=0;i<168;i++) { //Progressive roundoff
n =ceil(simplex.getCurrentValue(Pct[i]));
// Fix variable and reoptimize
simplex.add(Pct[i] == n);
}
m.out() << “Number of Pcts needed is “ << Z << endl;
m.end();
} 69 Solution
This code finds a solution with 208 workers in a couple of seconds. The optimum is 207.
The heuristic works well in part because if there were no lunch breaks, it would find the guaranteed optimal solution
[Bartholdi,Ratliffe,Orlin]
70 2. Constraint Programming LP/MIP is Beautiful, except when Variable domain information is important to the search strategy
especially critical in scheduling The problem variables range over symbolic entities and there are lots of symmetries
timetabling The MIP representation can be too verbose or awkward
configuration There are just too many constraints
e.g. vehicle routing 72 Mathematical Basis of Constraint Programming (CP)
The Constraint Satisfaction Problem:
Suppose a finite set of variables is given and with each variable is associated a nonempty finite domain.
A constraint on k variables X1,…,Xk is a relation R(X1,…,Xk) D1 x …x Dk.
A constraint satisfaction problem (CSP) is given by a finite set of constraints.
A solution to a CSP is an assignment of values to all the variables so that the constraints are satisfied. 73 Domain Reduction In CP, each constraint of a CSP is considered as a subproblem and techniques are developed for handling frequently encountered constraints.
With each constraint is associated a domain reduction algorithm which reduces the domains of the variables that occur in the constraint.
Accelerates convergence toward a solution
Detects infeasibility
74 Constraint Propagation The other key issue is communication among the constraints or subproblems.
The basic method used is called constraint propagation which links the constraints through their shared variables.
The important thing about this setup is that it is very modular and independent of the particular structure of the individual constraints. Monsieur Jordan Phenomenon Like prose, you have been doing constraint propagation all your life.
Crossword puzzles
Incomplete and so backtracking is needed
NY Times Sunday Crossword
Optical Illusions
Origin: Vision analysis (Marr,Waltz et al)
