Transcript Sanya-Conf3

Perspective of mathematical
optimization and its applications
Tokyo University of Marine Science
and Technology
Mikio Kubo
How to Solve Real Combinatorial
Optimization Problems Quickly
•
•
•
•
Mixed Integer Programming (MIP) Solver
Constraint Programming (CP) Solver
Scheduling Solver
(or develop (meta)heuristics)
... using Python Language
Why Python?
• We can do anything by
importing some modules
• Optimization
import gurobipy (MIP)
import SCOP (CP)
• Draw graphs
import networkX
• Also fly!
import antigravity ?
http://xkcd.com/353
/
Mixed Integer Programming (MIP)
• Variables
x : Real or Integer or Binary
• Constraints
Linear or (convex) Quadratic Expressions
minimize c’x+x’Qx (objective function)
subject to Ax=b
(constraints)
What’s Gurobi?
MIP solver
Developed by: Zonghao Gu, Edward Rothberg，Robert Bixby
Current version 4.6.1
Free academic license
Gurobi Objects
GRBError
addVar
Variable
Model
addSOS
addConstr
Column
Constraint
SOS
Callbacks
LinExpr
QuadExpr
Introduction to Gurobi (1)
• Create a model object
model = Model("Wine Blending")
Introduction to Gurobi (2)
• Add variable objects
x1 = model.addVar(name="x1")
x2 = model.addVar(name="x2")
x3 = model.addVar(name="x3")
• Model update
(needed before adding constraints; lazy update!)
model.update()
Introduction to Gurobi (3)
• Set the objective
model.setObjective(15*x1 + 18*x2 + 30*x3,
GRB.MAXIMIZE)
• Add constraints
model.addConstr(2*x1 + x2 + x3 <= 60)
model.addConstr(x1 + 2*x2 + x3 <= 60)
model.addConstr(x3 <= 30)
• Optimize
model.optimize()
Modeling with Lists
• Add variable objects into list
x=[ ]
for i in range(1,4):
var=model.addVar(name=“x[%s]”%i)
x.append(var)
• Add constraint “x1 + x2 + x3 <= 2”
model.addConstr( sum(x) <= 2 ) or
model.addConstr( quicksum(x) <= 2 )
X[1]
X[2]
X[3]
・・・
Modeling with Dictionaries
• Dictionary that maps keys (“Dry”, “Medium”,
“Sweet”) to variable objects
x={ }
x[“Dry”]= model.addVar(name=“Dry”)
x[“Medium”]= model.addVar(name=“Medium”)
x[“Sweet”]= model.addVar(name=“Sweet”)
Value
Key
“Hello”,
“Dry Wine”
Mapping
“Nihao”
Variable Object
Modeling with Dictionaries
• Add constraint “2 x1 + x2 + x3 <= 30”
model.addConstr( 2*x[“Dry”]+ x[“Medium”]
+x[“Sweet”] <=30 )
Blends, Profit =
multidict({"Dry":15, "Medium":18, "Sweet":30})
=> Blends=["Dry", "Medium“, "Sweet“]
Profit[“Dry”]=15, Profit[“Medium”]=18, ...
k-median problem
• A facility location problem with min-sum
objective function
• Number of customers n=200
• Number of facilities selected from customer
sites k=20
Formulation
week formulation
Python Code（1）
from gurobipy import *
model = Model("k-median")
x, y = {}, {}
# empty dictionaries
Dictionary Data Structure
Key
“Hanako”,
(1,2)
Mapping
Value
“127cm”
Variable Object
Python Code （２）
Add variable objects
I=range(n)
J=range(n)
for j in J:
“B” means binary variable
or GRB.BINARY
y[j] = model.addVar(vtype="B", name="y[%s]"%j)
for i in I:
x[i,j] =model.addVar( vtype="B",name="x[%s,%s]"%(i,j))
model.update()
Set the objective
model.setObjective(quicksum(c[i,j]*x[i,j] for i in I for j in J))
Python Code （３）
for i in I:
model.addConstr(quicksum(x[i,j] for j in J) = = 1, "Assign[%s]"%i)
for j in J:
model.addConstr(x[i,j] <= y[j], "Strong[%s,%s]"%(i,j))
model.addConstr(quicksum(y[j] for j in J) = = k, "k_median")
Weak formulation (result)
n=200,k=20
Optimize a model with 401 Rows, 40200 Columns and 80400
NonZeros
…
Explored 1445 nodes (63581 simplex iterations) in 67.08 seconds
Thread count was 2 (of 2 available processors)
Optimal solution found (tolerance 1.00e-04)
Best objective 1.0180195861e+01, best bound 1.0179189780e+01,
gap 0.0099%
Opt.value= 10.1801958607
Upper and lower bounds
(Weak Formulation)
18
16
Obj. Func. Value
14
12
10
8
6
4
2
0
0
10
20
30
40
CPU
50
60
70
Strong formulation (result)
Optimize a model with 40401 Rows, 40200 Columns and 160400
NonZeros
…
Explored 0 nodes (1697 simplex iterations) in 3.33 seconds
(No branching！）
Thread count was 2 (of 2 available processors)
Optimal solution found (tolerance 1.00e-04)
Best objective 1.0180195861e+01, best bound 1.0180195861e+01,
gap 0.0%
Opt.value= 10.1801958607
k-center problem
• A facility location problem with min-max
object
• n=100 customers，k=10 facilities
k-center (n=30,k=3)
k-median (n=30,k=3)
Formulation
Upper and lower
bounds
(n=100,k=10)
1.2
Obj. Fun. Value
1
0.8
0.6
0.4
0.2
0
0
50
100
150
200
CPU Time
250
300
350
400
k-Covering Problem
# of uncovered customers
=1 if customer is not covered
parameter that is =1
if distance is less
than or equal to θ
k-Covering+Binary Search
Upper and Lower Bounds UB， LB
while UB – LB >ε:
θ= (UB+LB)/2
if opt. val. of k-covering is 0 then
UB = θ
else
LB = θ
Computational Experiments
Constraint Programming (CP)
• Variables
x has to be selected from a finite domain (set
of values)
• Constraints
Linear, (non-convex) Quadratic, All Different
or
Any Types of Combinatorial Expressions
Assignment Problem (MIP/CP)
• Assign three jobs A,B,C to three workers 1,2,3
• MIP formulation:
xij
Binary
• CP formulation : x[i] with domain {A,B,C}
AllDiff ( x[1], x[2], x[3] )
Constraint Programming Solver
SCOP (Solver for COnstraint or Programming)
developed by Prof. Ibaraki and Prof. Nonobe
• ITC (International Timetabling Competition) 2007 –
Finalist for all 3 tracks
(3rd, 2nd, 3rd among 5 finalists)
• International Nurse Rostering Competition (INRC)
2010 – Finalists for all 3 tracks
(2nd,3rd, 4th among 5 finalists)
SCOP Objects
addVariable(s)
Model
addConstraint
Variable
Linear
Quadratic
Alldiff
Scheduling
• Activities (=Variables)
x has to be selected from a set of modes
(=domain of CP)
• Resource
Renewable or Non-renewable Resources
(=Constraints)
• Temporal Constraints
Scheduling Solver
OptSeq II
developed by Prof. Ibaraki and Prof. Nonobe
Multi-mode RCPSP
PSPLIB [Kolisch and Sprecher, 1997]
Algorithms
CPU
sec.
# of Feasible
Solutions
Error from
Best Known
Tabu search1
30
95/270
284.07%
Priority-rule method2
30
270/270
180.05%
Our tabu search3
10
269/270
95.88%
1. [De Reyck and Herroelen, 1999] 333MHz PC
2. [Heilmann, 2001] 333MHz PC
3. 1GHz PC
OptSeq Objects
addActivity
Attribute
addMode
Model
addResource
addTemporal
Mode
Resource
Temporal
Applications
• Train scheduling in a steel plant:
Flow optimization using Gurobi +
Detailed scheduling using OptSeq
• Supply Chain Modeling Language (SCML)
What’s SCML?
Supply Chain
Optimization
Models
SCML
SCML.py
Combinatorial
Optimization
Models
Solvers
(metaheuristics,
MIP/CP solvers)
Supply Chain Optimization Models
•
•
•
•
•
•
•
resource constrained scheduling
lot-sizing
logistics network design
safety stock allocation
economic order quantity
inventory policy optimization
vehicle routing
謝謝
Thank You
ご清聴ありがとうございました