Log Opt Blog

SCOP 5th Example: traveling salesman problem

admin — Tue, 05 Jul 2011 05:48:22 +0000

SCOP is a constrained programming solver.
In the example we call SCOP from Python language.

In the graph the number is the distances between locations and the green line is the optimal solution.

The problem is to find a shortest possible tour that visits each location exactly once.

The Python code can be written as follows:
************************************
""" tsp-scop.py: Using SCOP for solving the traveling salesman problem Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011 """

from scop2 import * m=Model()

cities=["T","L","M","R","B"] d=[[0,476,774,434,408],[476,0,784,894,569],[774,784,0,852,1154],[434,894,852,0,569],[408,569,1154,569,0]] n=len(cities)


varlist=m.addVariables(cities,range(n))

con1=Alldiff("AD",varlist,"inf") m.addConstraint(con1)

obj=Quadratic("obj") for i in range(n): for j in range(n): if i!=j: for k in range(n): if k ==n-1: ell=0 else: ell=k+1 obj.addTerms(d[i][j],varlist[i],k,varlist[j],ell) m.addConstraint(obj)


m.Params.TimeLimit=1

sol,violated=m.optimize()
print "solution"

for x in sol:

    print x,sol[x]

print "violated constraint(s)"

for v in violated:

    print v,violated[v]

************************************

We get the following result:

************************************

##solution

##B  2

##R  0

##M  4

##T  1

##L  3

##violated constraint(s)

##obj  3047

************************************



SCOP 4th Example: quadratic assignment problem
admin — Mon, 04 Jul 2011 09:12:46 +0000
SCOP is a constrained programming solver.

In the example we call SCOP from Python language.

graph (A) is the flow between facilities.

graph (B) is the distances of locations.
The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows.
The Python code can be written as follows:

************************************

"""

Using SCOP for solving the quadratic assignment problem

Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011

"""
from scop2 import *

m=Model()
n=3

d=[[0,2,3],[2,0,1],[3,1,0]]

f=[[0,5,1],[5,0,2],[1,2,0]]

nodes=["n"+str(i) for i in range(n)]

varlist=m.addVariables(nodes,range(n))
con1=Alldiff("AD",varlist,"inf")

m.addConstraint(con1)
obj=Quadratic("obj")

for i in range(n-1):

    for j in range(i+1,n):

        for k in range(n):

            for ell in range(n):

                if k !=ell:

                    obj.addTerms(f[i][j]*d[k][ell],varlist[i],k,varlist[j],ell)

m.addConstraint(obj)

m.Params.TimeLimit=1

sol,violated=m.optimize()
print "solution"

for x in sol:

    print x,sol[x]

print "violated constraint(s)"

for v in violated:

    print v,violated[v]

************************************

We get the following result:

************************************

##solution

##n0  2

##n1  1

##n2  0

##violated constraint(s)

##obj  12

************************************



OptSeq 5th Example: Resource Constrained Scheduling
admin — Mon, 20 Jun 2011 07:44:07 +0000
Here, we introduce the 5th example of OptSeq Python module.
Consider a 4-activity problem with a resource whose capacity is 2 units on day 1, 2, 4, 5, 6, and 1 unit on day 3.

The processing times (durations) of the activities are kept in the dictionary

 duration ={1:1,2:3,3:2,4:2}.

Precedence constraints are give by:

 Activity 1 -> Activity 2;

 Activity 1 -> Activity 3;

 Activity 2 -> Activity 4.

Activity 1 requires 2 units of resource the first day.

Activity 2 requires 2 units of resource the first day and 1 unit on other days.

Activity 3 requires 1 unit of resource all the days.

Activity 4 requires 1 unit of the resource the first day and 2 units on the second day.

The objective is to find the maximum completion time (makespan).

graph (A) is the problem.

graph (B) is the solution.
Now the Python code can be written as follows:

******************************************

from optseq2 import *

m1=Model()

duration ={1:1,2:3,3:2,4:2}

req={}

req[1]={(0,1):2 }

req[2]={(0,1):2 ,(1,3):1}

req[3]={(0,2):1 }

req[4]={(0,1):1,(1,2):2 }
res=m1.addResource("worker")

res.addCapacity(0,2,2)

res.addCapacity(2,3,1)

res.addCapacity(3,"inf",2)
act={}

mode={}
for i in duration:

    act[i]=m1.addActivity("Act[%s]"%i)

    mode[i]=Mode("Mode[%s]"%i,duration[i])

    mode[i].addResource(res,req[i])

    act[i].addModes(mode[i])

m1.addTemporal(act[1],act[2])

m1.addTemporal(act[1],act[3])

m1.addTemporal(act[2],act[4])

m1.Params.TimeLimit=1

m1.Params.Makespan=True

m1.Params.OutputFlag=True

m1.optimize()

******************************************
We get the following result:

******************************************

##source --- 0 0

##sink --- 6 6

##Act[1] --- 0 1

##Act[2] --- 1 4

##Act[3] --- 3 5

##Act[4] --- 4 6

##planning horizon= 6

******************************************



SCOP 3rd Example: graph coloring problem
admin — Thu, 02 Jun 2011 07:02:17 +0000
SCOP is a constrained programming solver.

In the example we call SCOP from Python language.


   A     B 

The problem is to label the graph’s vertices (6 vertices) with colors (in this example, we use 3 colors) such that no two vertices sharing the same edge have the same color.
graph (A) is the problem.

graph (B) is the solution.
The Python code can be written as follows:

************************************

"""

Using SCOP for solving the graph coloring problem

Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011

"""
from scop2 import *

m=Model()
K=3

nodes=["n"+str(i) for i in range(6)]

adj=[[2],[3],[0,3,4,5],[1,2,5],[2],[2,3]]

n=len(nodes)
varlist=m.addVariables(nodes,range(K))
for i in range(n):

    for j in adj[i]:

        if i < j:

            con1=Alldiff("alldiff"+str(i)+str(j),[varlist[i],varlist[j]],"inf")

            m.addConstraint(con1)

m.Params.TimeLimit=1

sol,violated=m.optimize()
print "solution"

for x in sol:

    print x,sol[x]

print "violated constraint(s)"

for v in violated:

    print v,violated[v]

************************************

We get the following result:

************************************

##solution

##n0  0

##n1  0

##n2  1

##n3  2

##n4  2

##n5  0

##violated constraint(s)

************************************



SCOP 2nd Example: graph partitioning problem
admin — Mon, 14 Mar 2011 14:16:13 +0000
SCOP is a constrained programming solver.

In the example we call SCOP from Python language.

graph (A) is the problem.

graph (B) is the solution.
The Python code can be written as follows:

************************************

"""

Using SCOP for solving the graph partitioning problem

Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011

"""
from scop2 import *

m=Model()
nodes=["n"+str(i) for i in range(6)]

adj=[[1,4],[0,2,4],[1],[4,5],[0,1,3,5],[3,4]]

n=len(nodes)
varlist=m.addVariables(nodes,[0,1])
con1=Linear("constraint","inf",n/2,"=")

for i in range(len(nodes)):

    con1.addTerms(1,varlist[i],1)

m.addConstraint(con1)

con2=Quadratic("obj")

for i in range(n):

    for j in adj[i]:

        con2.addTerms(1,varlist[i],1,varlist[j],0)

        con2.addTerms(1,varlist[i],0,varlist[j],1)

m.addConstraint(con2)

m.Params.TimeLimit=1

sol,violated=m.optimize()
print "solution"

for x in sol:

    print x,sol[x]

print "violated constraint(s)"

for v in violated:

    print v,violated[v]

************************************
We get the following result:

************************************

##solution

##n0  0

##n1  0

##n2  0

##n3  1

##n4  1

##n5  1

##violated constraint(s)

##obj  4

************************************



OptSeq 4th Example: Parallel Shop Problem using Modes
admin — Mon, 14 Mar 2011 13:12:32 +0000
Here, we introduce the 4th example of OptSeq Python module.
Consider a 10-activity problem in which each activity is processed on three identical parallel machines.

The processing times (durations) of the activities are kept in the dictionary

 duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }.

Precedence constraints are given by:

 Activity 1 -> Activity 9;

 Activities 5,6,7,8 are processed after Activity 4 and before Activity 10.

Activity 1 can be processed in one of the following three modes:

 Mode 1 with duration 3 that requires 1 unit of worker resource,

 Mode 2 with duration 2 that requires 2 units of worker resource, and

 Mode 3 with duration 1 that requires 3 units of worker resource.

The objective is to find the maximum completion time (makespan).
Now the Python code can be written as follows:

******************************************

from optseq2 import *

m1=Model()

duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }

res=m1.addResource("worker",capacity={(0,"inf"):3})

act={}

mode={}
for i in duration:

    act[i]=m1.addActivity("Act[%s]"%i)

    if i==1:

        mode[1,1]=Mode("Mode[1_1]",3)

        mode[1,1].addResource(res,{(0,"inf"):1})

        mode[1,2]=Mode("Mode[1_2]",2)

        mode[1,2].addResource(res,{(0,"inf"):2})

        mode[1,3]=Mode("Mode[1_3]",1)

        mode[1,3].addResource(res,{(0,"inf"):3})

        act[i].addModes(mode[1,1],mode[1,2],mode[1,3])

    else:

        mode[i]=Mode("Mode[%s]"%i,duration[i])

        mode[i].addResource(res,{(0,"inf"):1})

        act[i].addModes(mode[i])

#temporal (precedense) constraints

m1.addTemporal(act[1],act[9])

for i in range(5,9):

    m1.addTemporal(act[4],act[i])

    m1.addTemporal(act[i],act[10])

m1.Params.TimeLimit=1

m1.Params.Makespan=True

m1.optimize()

******************************************
We get the following result:

******************************************

##source --- 0 0

##sink --- 13 13

##Act[1] Mode[1_3] 0 1

##Act[2] --- 1 3

##Act[3] --- 11 13

##Act[4] --- 1 3

##Act[5] --- 7 11

##Act[6] --- 3 7

##Act[7] --- 7 11

##Act[8] --- 3 7

##Act[9] --- 1 12

##Act[10] --- 11 13

##planning horizon= 13

******************************************



OptSeq 3rd Example: Parallel Shop Problem
admin — Sun, 13 Mar 2011 18:21:13 +0000
Here, we introduce the 3rd example of OptSeq Python module.
Consider a 10-activity problem in which each activity is processed on three identical parallel machines.

The processing times (durations) of the activities are kept in the dictionary

 duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }.

Precedence constraints are given by:

 Activity 1 -> Activity 9;

 Activities 5,6,7,8 are processed after Activity 4 and before Activity 10.

The objective is to find the maximum completion time (makespan).
Now the Python code can be written as follows:

******************************************

from optseq2 import *

m1=Model()

duration ={1:3, 2:2, 3:2, 4:2, 5:4, 6:4, 7:4, 8:4, 9:11, 10:2 }

res=m1.addResource("worker",capacity={(0,"inf"):3})

act={}

mode={}

for i in duration:

    act[i]=m1.addActivity("Act[%s]"%i)

    mode[i]=Mode("Mode[%s]"%i,duration[i])

    mode[i].addResource(res,{(0,"inf"):1})

    act[i].addModes(mode[i])

#temporal (precedense) constraints

m1.addTemporal(act[1],act[9])

for i in range(5,9):

    m1.addTemporal(act[4],act[i])

    m1.addTemporal(act[i],act[10])

m1.Params.TimeLimit=1

m1.Params.Makespan=True

m1.optimize() 

******************************************
We get the following result:

******************************************

##source --- 0 0

##sink --- 14 14

##Act[1] --- 0 3

##Act[2] --- 0 2

##Act[3] --- 0 2

##Act[4] --- 2 4

##Act[5] --- 8 12

##Act[6] --- 4 8

##Act[7] --- 8 12

##Act[8] --- 4 8

##Act[9] --- 3 14

##Act[10] --- 12 14

##planning horizon= 14

******************************************



OptSeq 2nd Example: PERT with resource constraint
admin — Sun, 13 Mar 2011 14:20:15 +0000
Here, we introduce the 2nd example of OptSeq Python module.
Consider a 5-activity problem with precedence constraints between the activities.

The processing times (durations) of the activities are kept in the dictionary

 duration ={1:13, 2:25, 3:15, 4:27, 5:22 }.

Precedence constraints are given by:

 Activity 1 -> Activity 3; Activity 2 -> Activity 4;

 Activity 3 -> Activity 4; and Activity 3 -> Activity 5.

Each activity requires one unit of worker resource whose capacity (maximum amount of availability for each time period) is 1.

The objective is to find the maximum completion time (makespan) for all 5 activities
Now the Python code can be written as follows:

******************************************

from optseq2 import *

m1=Model()

duration ={1:13, 2:25, 3:15, 4:27, 5:22 }

res=m1.addResource("worker",capacity={(0,"inf"):1})

act={}

mode={}  
for i in duration: 

    act[i]=m1.addActivity("Act[%s]"%i)

    mode[i]=Mode("Mode[%s]"%i,duration[i])

    mode[i].addResource(res,{(0,"inf"):1})

    act[i].addModes(mode[i])

#temporal (precedense) constraints

m1.addTemporal(act[1],act[3])

m1.addTemporal(act[2],act[4])

m1.addTemporal(act[2],act[5])

m1.addTemporal(act[3],act[4])
m1.Params.TimeLimit=1

m1.Params.OutputFlag=True

m1.Params.Makespan=True

m1.optimize()

******************************************
We get the following result:

******************************************

##source --- 0 0

##sink --- 102 102

##Act[1] --- 47 60

##Act[2] --- 0 25

##Act[3] --- 60 75

##Act[4] --- 75 102

##Act[5] --- 25 47

##planning horizon= 102

******************************************



AMPL問題例７：グラフ分割問題
admin — Sat, 12 Mar 2011 16:21:01 +0000
**以下に記述するAMPLモデルとデータには漢字コメントを使用しているため，そのまま実行するとエラーします．コピーして実行するときはコメント文を削除して下さい．**
問題概要

６つの点を L と R の２つのグループに等分割しようとする．

点と点の間には図 A のように枝がある．

L と R をまたぐ枝の数が最小になるように等分割するにはどのように分ければよいのか．

図 B は最適解．

以下はAMPLのモデルです．
***********************************

param n ;　　　　　　　　　#点の数
set V := {0 .. n-1};     　　　#点の集合

set E within {V,V};      　　　#枝の集合
var x {V} binary;　　　　　#点 i が L 側に含まれるとき１，その他のとき（R 側に含まれるとき）０

var y {E} binary ;　　　　　#枝が L と R をまたいでいるとき１，その他のとき０
minimize Adjacency: 　　

sum{(i,j) in E}y[i,j] ;　　　　　# L と R をまたぐ枝の本数を最小化
subject to constraint1:

sum{i in V} x[i] = n/2 ;　　　　　#等分割を表す制約
subject to constraint2 {(i,j) in E} :

x[i]-x[j]<=y[i,j] ;　　　　　　　　　　　　　　　

# i が L に入っていて，j が L に入っていないとき y[i,j] が 1 になることを規定する制約
subject to constraint3 {(i,j) in E} :

x[j]-x[i]<=y[i,j] ;

# ｊ が L に入っていて，i が L に入っていないとき y[i,j] が 1 になることを規定する制約

***********************************
以下はAMPLのデータです．
***********************************

param n =6 ;

set E := 0 1  0 4  1 2  1 4  3 4  3 5  4 5 ;

***********************************



AMPL問題例６：箱詰め問題（ビンパッキング問題）
admin — Fri, 11 Mar 2011 13:26:56 +0000
**以下に記述するAMPLモデルとデータには漢字コメントを使用しているため，そのまま実行するとエラーします．コピーして実行するときはコメント文を削除して下さい．**
問題概要

ビン：１３個，入れられる上限重量９ｋｇ

アイテム：２０個，各アイテムの重量はＡＭＰＬデータのパラメータ ｓ の通り

アイテムをどのようにビンに入れれば必要なビンの数を最小化できるのか．
以下はAMPLのモデルです．
***********************************

param Item ;　　　　　　　　　　#アイテムの数

param Bins ;　　　　　　　　　　#ビンの数
set I:={1 .. Item} ; 　　　　#アイテムの集合

set J:={1 .. Bins} ; 　　　　#ビンの集合
param B ;　　　　　　　　　　　　#ビンの重さ

param s {I} ;　　　　　　　　　#アイテムの重さ
var x {I,J} binary;　　　　　　#アイテム i をビン j に入れるとき１，その他のとき０

var y {J} binary ;　　　　　　#ビン j を使うとき１，その他のとき０
minimize Bins_Num:

 sum{j in J}y[j] ;　　　　　　　#ビンの数を最小化
subject to Assign {i in I}:

sum{j in J}x[i,j]=1 ;　　　　　#アイテムは必ずビンに割り当てられなければならない
subject to Capacity {j in J} :

sum{i in I} s[i]*x[i,j]<=B*y[j] ;　　#各ビンに入れるアイテムの合計重量はビンの上限重量以下
subject to Tighten_Con {i in I, j in J} :　

x[i,j] <= y[j] ;　　　　　　　　　#ビンを使用しないときはアイテムは入れられない

***********************************
以下はAMPLのデータです．
***********************************

param Item:= 20 ;

param Bins:=13 ;

param B :=9 ;

param s :=

1 6

2 6

3 5

4 5

5 5

6 4

7 4

8 4

9 4

10 2

11 2

12 2

13 2

14 3

15 3

16 7

17 7

18 5

19 8

20 8

;

***********************************