| sched_main.mos |
(!****************************************************************
CP example problems
===================
file sched_main.mos
```````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
Combined MIP-CP problem solving: cut generation for MIP model
by solving CP subproblems at nodes in the MIP branching tree.
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, March 2005, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + CP) master problem"
uses "mmsystem", "mmxprs", "mmjobs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 1
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of operations (products)
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totCP: real ! Time measurement
ctrun: integer ! Counter of CP runs
CPmodel: Model ! Reference to the CP sequencing model
ev: Event ! Event
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
! **** Problem definition ****
define_MIP_model ! Definition of the MIP model
res:=compile("sched_sub.mos") ! Compile the CP model
load(CPmodel, "sched_sub.bim") ! Load the CP model
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
initializations to "raw:"
totsolve as "shmem:solvetime"
REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
initializations from "raw:"
totsolve as "shmem:solvetime"
end-initializations
writeln("Total CP solve time: ", totsolve)
writeln("Total CP time: ", totCP)
writeln("CP runs: ", ctrun)
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
setparam("XPRS_COLORDER", 2)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -200)
end-do
2: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
3: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
function solve_CP_problem(m: integer, ProdMach: set of integer,
mode: integer): boolean
declarations
DURm: dynamic array(range) of integer
sol: dynamic array(range) of integer
solvetime: real
end-declarations
! Data for CP model
forall(p in ProdMach) DURm(p):= DUR(p,m)
initializations to "raw:"
ProdMach as "shmem:ProdMach"
DURm as "shmem:DURm"
end-initializations
! Solve the problem and retrieve the solution if it is feasible
startsolve:= gettime
returned:= false
if(getstatus(CPmodel)=RT_RUNNING) then
fflush
writeln("CPmodel is running")
fflush
exit(1)
end-if
ctrun+=1
run(CPmodel, "NP=" + NP + ",VERBOSE=" + VERBOSE + ",MODE=" + mode)
wait ! Wait for a message from the submodel
ev:= getnextevent ! Retrieve the event
if getclass(ev)=EVENT_SOLVED then
returned:= true
if mode = 2 then
initializations from "raw:"
sol as "shmem:solstart"
end-initializations
forall(p in ProdMach) solstart(p):=sol(p)
end-if
elif getclass(ev)<>EVENT_FAILED then
writeln("Problem with Kalis")
exit(2)
end-if
wait
dropnextevent ! Ignore "submodel finished" event
totCP+= (gettime-startsolve)
end-function
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer, ProdMach: set of integer)
forall(p in PRODS) do
val:=getsol(use(p,m))
if (val > 0 and val < 1) then
ProdMach:={}
break
elif val>0.5 then
ProdMach+={p}
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Generate a cut for machine m if the sequencing subproblem is infeasible
function generate_cut_machine(m: integer): boolean
declarations
ProdMach: set of integer
end-declarations
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
! Solve the sequencing problem (CP model): if solved, save the solution,
! otherwise add an infeasibility cut to the MIP problem
size:= getsize(ProdMach)
returned:= false
if (size>1) then
if not solve_CP_problem(m, ProdMach, 1) then
Cut:= sum(p in ProdMach) use(p,m) - (size-1)
if VERBOSE > 2 then
writeln(m,": ", ProdMach, " <= ", size-1)
end-if
addcut(1, CT_LEQ, Cut)
returned:= true
end-if
end-if
end-function
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
returned:=false; ctcutold:=ctcut
forall(m in MACH) do
if generate_cut_machine(m) then
returned:=true ! Call function again for this node
ctcut+=1
end-if
end-do
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
ProdMach: set of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
forall(m in MACH) do
ProdMach:= {}
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
Size:= getsize(ProdMach)
if Size > 1 then
! (Re)solve the CP sequencing problem
if not solve_CP_problem(m, ProdMach, 2) then
writeln("Something wrong here: ", m, ProdMach)
end-if
elif Size=1 then
elem:=min(p in ProdMach) p
solstart(elem):=REL(elem)
end-if
end-do
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_sub.mos |
(!****************************************************************
CP example problems
===================
file sched_sub.mos
``````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
Combined MIP-CP problem solving: cut generation for MIP model
by solving CP subproblems at nodes in the MIP branching tree.
*** Not intended to be run standalone - run from sched_main.mos ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, March 2005
*****************************************************************!)
model "Schedule (MIP + CP) CP subproblem"
uses "kalis", "mmjobs" , "mmsystem"
parameters
VERBOSE = 1
NP = 12 ! Number of products
MODE = 1 ! 1 - decide feasibility
! 2 - return complete solution
end-parameters
startsolve:= gettime
declarations
PRODS = 1..NP ! Set of products
ProdMach: set of integer
end-declarations
initializations from "raw:"
ProdMach as "shmem:ProdMach"
end-initializations
finalize(ProdMach)
declarations
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
DURm: array(ProdMach) of integer ! Processing times on machine m
solstart: array(ProdMach) of integer ! Solution values for start times
start: array(ProdMach) of cpvar ! Start times of tasks
Disj: array(range) of cpctr ! Disjunctive constraints
Strategy: array(range) of cpbranching ! Enumeration strategy
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
solvetime: real
end-declarations
initializations from "raw:"
DURm as "shmem:DURm" REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
! Bounds on start times
forall(p in ProdMach) setdomain(start(p), REL(p), DUE(p)-DURm(p))
! Disjunctive constraint
ct:= 1
forall(p,q in ProdMach| p<q) do
Disj(ct):= start(p) + DURm(p) <= start(q) or start(q) + DURm(q) <= start(p)
ct+= 1
end-do
! Post disjunctions to the solver
nDisj:= ct; j:=1; res:= true
while (res and j<nDisj) do
res:= cp_post(Disj(j))
j+=1
end-do
! Solve the problem
if res then
Strategy(1):= settle_disjunction(Disj)
Strategy(2):= assign_and_forbid(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX,
start)
cp_set_branching(Strategy)
res:= cp_find_next_sol
end-if
! Pass solution to master problem
if res then
forall(p in ProdMach) solstart(p):= getsol(start(p))
if MODE=2 then
initializations to "raw:"
solstart as "shmem:solstart"
end-initializations
end-if
send(EVENT_SOLVED,0)
else
send(EVENT_FAILED,0)
end-if
! Update total running time measurement
initializations from "raw:"
solvetime as "shmem:solvetime"
end-initializations
solvetime+= gettime-startsolve
initializations to "raw:"
solvetime as "shmem:solvetime"
end-initializations
end-model
|
|
| sched_mainp.mos |
(!****************************************************************
CP example problems
===================
file sched_mainp.mos
````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of CP subproblems --
Combined MIP-CP problem solving: cut generation for MIP model
by solving CP subproblems at nodes in the MIP branching tree.
*** ATTENTION: This model will not run properly if no ***
*** sufficient number of Xpress licences is available. ***
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, March 2005, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + CP) master problem"
uses "mmsystem", "mmxprs", "mmjobs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 1
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of products
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer ! CP solution values
OpMach: array(MACH,PRODS) of integer ! Tasks assigned to machines
NumOp: array(MACH) of integer ! Number of tasks assigned to mach.s
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totCP,solveM: real ! Time measurement
ctrun: integer ! Iteration counter (CP)
CPmodel: array(MACH) of Model ! References to the CP models
ev: Event ! Event
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
! **** Problem definition ****
define_MIP_model ! Definition of the MIP model
res:=compile("sched_subp.mos") ! Compile the CP model
forall(m in MACH) do
load(CPmodel(m), "sched_subp.bim") ! Load the CP models
CPmodel(m).uid:= m ! Store the model indices
end-do
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
forall (m in MACH)
initializations to "raw:"
totsolve as "shmem:solvetime"+m
end-initializations
initializations to "raw:"
REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
forall (m in MACH) do
initializations from "raw:"
solveM as "shmem:solvetime"+m
end-initializations
totsolve += solveM
end-do
writeln("Total CP solve time: ", totsolve)
writeln("Total CP time: ", totCP)
writeln("CP runs: ", ctrun)
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
setparam("XPRS_COLORDER", 2)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
2: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
procedure start_CP_model(m: integer, mode: integer)
declarations
ProdMach: set of integer
DURm: array(ProdMach) of integer
end-declarations
! Data for CP model
forall(p in 1..NumOp(m)) ProdMach+={OpMach(m,p)}
forall(p in ProdMach) DURm(p):= DUR(p,m)
initializations to "raw:"
ProdMach as "shmem:ProdMach"+m
DURm as "shmem:DUR"+m
end-initializations
! Start solving the problem
if(getstatus(CPmodel(m))=RT_RUNNING) then
writeln(gettime-starttime, " CP model ", m, " is running")
fflush
exit(1)
end-if
ctrun+=1
run(CPmodel(m), "NP=" + NP + ",VERBOSE=" + VERBOSE + ",MODE=" + mode +
",M=" + m)
end-procedure
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer)
NumOp(m):=0
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
NumOp(m):=0
break
elif val>0.5 then
NumOp(m)+=1
OpMach(m,NumOp(m)):= p
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Add an infeasibility cut for machine m to the MIP problem
procedure add_cut_machine(m: integer)
Cut:= sum(p in 1..NumOp(m)) use(OpMach(m,p),m) - (NumOp(m)-1)
if VERBOSE > 1 then
write(m,": ")
forall(p in 1..NumOp(m)) write(OpMach(m,p), " ")
writeln(" <= ", NumOp(m)-1)
end-if
addcut(1, CT_LEQ, Cut)
end-procedure
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
declarations
ToSolve: set of integer
end-declarations
returned:=false; ctcutold:=ctcut; ctend:= 0
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 0 then ToSolve += {m}; end-if
end-do
! Start solving the CP sequencing models
startsolve:= gettime
forall(m in ToSolve) start_CP_model(m, 1)
! Retrieve all results/termination messages
if getsize(ToSolve) > 0 then
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: solved:=true ! Nothing to do
EVENT_FAILED: do
M:=ev.fromuid ! UID of model sending the event
add_cut_machine(M)
ctcut+=1
returned:=true ! Call cut gen. again for this node
end-do
else writeln("Problem with Kalis")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
end-if
totCP+= (gettime-startsolve)
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
sol: dynamic array(range) of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 1 then
ToSolve += {m}
elif NumOp(m) = 1 then
solstart(OpMach(m,1)):= REL(OpMach(m,1))
end-if
end-do
! Start solving the CP sequencing models
startsolve:= gettime
forall(m in ToSolve) start_CP_model(m, 2)
! Retrieve all results/termination messages
ctend:= 0
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: do
M:=ev.fromuid ! UID of model sending the event
initializations from "raw:"
sol as "shmem:solstart"+M
end-initializations
forall(p in 1..NumOp(M))
solstart(OpMach(M,p)):=sol(OpMach(M,p))
end-do
EVENT_FAILED: do
M:=ev.fromuid ! UID of model sending the event
writeln("Something wrong here: ", M, OpMach, NumOp)
end-do
else writeln("Problem with Kalis")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_subp.mos |
(!****************************************************************
CP example problems
===================
file sched_subp.mos
```````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of CP subproblems --
Combined MIP-CP problem solving: cut generation for MIP model
by solving CP subproblems at nodes in the MIP branching tree.
*** Not intended to be run standalone - run from sched_mainp.mos ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Apr. 2005
*****************************************************************!)
model "Schedule (MIP + CP) CP subproblem"
uses "kalis", "mmjobs" , "mmsystem"
parameters
VERBOSE = 1
M = 1 ! Number of the machine
NP = 12 ! Number of products
MODE = 1 ! 1 - decide feasibility
! 2 - return complete solution
end-parameters
startsolve:= gettime
declarations
PRODS = 1..NP ! Set of products
ProdMach: set of integer
end-declarations
initializations from "raw:"
ProdMach as "shmem:ProdMach"+M
end-initializations
finalize(ProdMach)
declarations
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
DURm: array(ProdMach) of integer ! Processing times on machine m
solstart: array(ProdMach) of integer ! Solution values for start times
start: array(ProdMach) of cpvar ! Start times of tasks
Disj: array(range) of cpctr ! Disjunctive constraints
Strategy: array(range) of cpbranching ! Enumeration strategy
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
solvetime: real
end-declarations
initializations from "raw:"
DURm as "shmem:DUR"+M REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
! Bounds on start times
forall(p in ProdMach) do
REL(p) <= start(p); start(p) <= DUE(p)-DURm(p)
end-do
! Disjunctive constraint
ct:= 1
forall(p,q in ProdMach| p<q) do
Disj(ct):= start(p) + DURm(p) <= start(q) or start(q) + DURm(q) <= start(p)
ct+= 1
end-do
! Post disjunctions to the solver
nDisj:= ct; j:=1; res:= true
while (res and j<nDisj) do
res:= cp_post(Disj(j))
j+=1
end-do
! Solve the problem
if res then
Strategy(1):= settle_disjunction(Disj)
Strategy(2):= assign_and_forbid(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX,
start)
cp_set_branching(Strategy)
res:= cp_find_next_sol
end-if
! Pass solution to master problem
if res then
forall(p in ProdMach) solstart(p):= getsol(start(p))
if MODE=2 then
initializations to "raw:"
solstart as "shmem:solstart"+M
end-initializations
end-if
send(EVENT_SOLVED,0)
else
send(EVENT_FAILED,0)
end-if
! Update total running time measurement
initializations from "raw:"
solvetime as "shmem:solvetime"+M
end-initializations
solvetime+= gettime-startsolve
initializations to "raw:"
solvetime as "shmem:solvetime"+M
end-initializations
end-model
|
|
| sched_mainpd.mos |
(!****************************************************************
CP example problems
===================
file sched_mainpd.mos
`````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of CP subproblems --
-- Distributed computing version --
Combined MIP-CP problem solving: cut generation for MIP model
by solving CP subproblems at nodes in the MIP branching tree.
Before running this model, you need to set up the list
NODES with machine names/addresses of your local network.
All nodes that are used need to have the same version of
Xpress installed and suitably licensed, and the server
"xprmsrv" must have been started on these machines.
All files are local to the root node, no write access is
required at remote nodes.
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + CP) master problem"
uses "mmsystem", "mmxprs", "mmjobs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 1
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of products
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer ! CP solution values
OpMach: array(MACH,PRODS) of integer ! Tasks assigned to machines
NumOp: array(MACH) of integer ! Number of tasks assigned to mach.s
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totCP,solveM: real ! Time measurement
ctrun: integer ! Iteration counter (CP)
CPmodel: array(MACH) of Model ! References to the CP models
ev: Event ! Event
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
NODES: list of string ! Set of available nodes
nodeInst: dynamic array(set of string) of Mosel ! Mosel instances on remote nodes
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
!**** Setting up remote Mosel instances ****
sethostalias("thiscomp","rcmd:")
NODES:= ["","thiscomp"]
!!! This list must have at least 1 element.
!!! Use machine names within your local network, IP addresses, or
!!! empty string for the current node running this model.
forall(n in NODES, nct as counter) do
create(nodeInst(n))
if connect(nodeInst(n), n)<>0 then exit(1); end-if
if nct>= NM then break; end-if ! Stop when started enough
end-do
! **** Problem definition ****
define_MIP_model ! Definition of the MIP model
res:=compile("sched_subpd.mos") ! Compile the CP model
if res<>0 then exit(2); end-if
ct:=0
forall(m in MACH) do
ct:= if(ct<NODES.size, ct+1, 1) ! Get next node in list or restart
n:= getlast(gethead(NODES,ct)) ! from beginning when end is reached
load(nodeInst(n), CPmodel(m), "rmt:sched_subpd.bim") ! Load the CP models
CPmodel(m).uid:= m ! Store the model indices
end-do
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
forall (m in MACH)
initializations to "time_"+m+".dat"
totsolve as "solvetime"
end-initializations
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
forall (m in MACH) do
initializations from "time_"+m+".dat"
solveM as "solvetime"
end-initializations
totsolve += solveM
end-do
writeln("Total CP solve time: ", totsolve)
writeln("Total CP time: ", totCP)
writeln("CP runs: ", ctrun)
fdelete("sched_subpd.bim") ! Cleaning up
forall(m in MACH) fdelete("sol_"+m+".dat")
forall(m in MACH) fdelete("sol_"+m+".dat~")
forall(m in MACH) fdelete("time_"+m+".dat")
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
setparam("XPRS_COLORDER", 2)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
2: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
procedure start_CP_model(m: integer, mode: integer)
declarations
ProdMach: set of integer
DURm: array(ProdMach) of integer
end-declarations
! Data for CP model
forall(p in 1..NumOp(m)) ProdMach+={OpMach(m,p)}
forall(p in ProdMach) DURm(p):= DUR(p,m)
initializations to "sol_"+m+".dat"
ProdMach
DURm
end-initializations
! Start solving the problem
if(getstatus(CPmodel(m))=RT_RUNNING) then
writeln(gettime-starttime, " CP model ", m, " is running")
fflush
exit(1)
end-if
ctrun+=1
run(CPmodel(m), "NP=" + NP + ",VERBOSE=" + VERBOSE + ",MODE=" + mode +
",M=" + m + ",DATAFILE=" + DATAFILE)
end-procedure
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer)
NumOp(m):=0
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
NumOp(m):=0
break
elif val>0.5 then
NumOp(m)+=1
OpMach(m,NumOp(m)):= p
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Add an infeasibility cut for machine m to the MIP problem
procedure add_cut_machine(m: integer)
Cut:= sum(p in 1..NumOp(m)) use(OpMach(m,p),m) - (NumOp(m)-1)
if VERBOSE > 1 then
write(m,": ")
forall(p in 1..NumOp(m)) write(OpMach(m,p), " ")
writeln(" <= ", NumOp(m)-1)
end-if
addcut(1, CT_LEQ, Cut)
end-procedure
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
declarations
ToSolve: set of integer
end-declarations
returned:=false; ctcutold:=ctcut; ctend:= 0
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 0 then ToSolve += {m}; end-if
end-do
! Start solving the CP sequencing models
startsolve:= gettime
forall(m in ToSolve) start_CP_model(m, 1)
! Retrieve all results/termination messages
if getsize(ToSolve) > 0 then
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: solved:=true ! Nothing to do
EVENT_FAILED: do
M:=ev.fromuid ! UID of model sending the event
add_cut_machine(M)
ctcut+=1
returned:=true ! Call cut gen. again for this node
end-do
else writeln("Problem with Kalis")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
end-if
totCP+= (gettime-startsolve)
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
sol: dynamic array(range) of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 1 then
ToSolve += {m}
elif NumOp(m) = 1 then
solstart(OpMach(m,1)):= REL(OpMach(m,1))
end-if
end-do
! Start solving the CP sequencing models
startsolve:= gettime
forall(m in ToSolve) start_CP_model(m, 2)
! Retrieve all results/termination messages
ctend:= 0
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: do
M:=ev.fromuid ! UID of model sending the event
initializations from "sol_"+M+".dat"
sol
end-initializations
fdelete("sol_"+M+".dat")
forall(p in 1..NumOp(M))
solstart(OpMach(M,p)):=sol(OpMach(M,p))
end-do
EVENT_FAILED: do
M:=ev.fromuid ! UID of model sending the event
writeln("Something wrong here: ", M, OpMach, NumOp)
end-do
else writeln("Problem with Kalis")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_subpd.mos |
(!****************************************************************
CP example problems
===================
file sched_subpd.mos
````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of CP subproblems --
-- Distributed computing version --
Combined MIP-CP problem solving: cut generation for MIP model
by solving CP subproblems at nodes in the MIP branching tree.
*** Not intended to be run standalone - run from sched_mainpd.mos ***
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010
*****************************************************************!)
model "Schedule (MIP + CP) CP subproblem"
uses "kalis", "mmjobs" , "mmsystem"
parameters
DATAFILE = "sched_3_12.dat"
VERBOSE = 1
M = 1 ! Number of the machine
NP = 12 ! Number of products
MODE = 1 ! 1 - decide feasibility
! 2 - return complete solution
end-parameters
startsolve:= gettime
declarations
PRODS = 1..NP ! Set of products
ProdMach: set of integer
end-declarations
initializations from "rmt:sol_"+M+".dat"
ProdMach
end-initializations
finalize(ProdMach)
declarations
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
DURm: array(ProdMach) of integer ! Processing times on machine m
solstart: array(ProdMach) of integer ! Solution values for start times
start: array(ProdMach) of cpvar ! Start times of tasks
Disj: array(range) of cpctr ! Disjunctive constraints
Strategy: array(range) of cpbranching ! Enumeration strategy
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
solvetime: real
end-declarations
initializations from "rmt:sol_"+M+".dat"
DURm
end-initializations
initializations from "rmt:"+DATAFILE
REL DUE
end-initializations
! Bounds on start times
forall(p in ProdMach) do
REL(p) <= start(p); start(p) <= DUE(p)-DURm(p)
end-do
! Disjunctive constraint
ct:= 1
forall(p,q in ProdMach| p<q) do
Disj(ct):= start(p) + DURm(p) <= start(q) or start(q) + DURm(q) <= start(p)
ct+= 1
end-do
! Post disjunctions to the solver
nDisj:= ct; j:=1; res:= true
while (res and j<nDisj) do
res:= cp_post(Disj(j))
j+=1
end-do
! Solve the problem
if res then
Strategy(1):= settle_disjunction(Disj)
Strategy(2):= assign_and_forbid(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX,
start)
cp_set_branching(Strategy)
res:= cp_find_next_sol
end-if
! Pass solution to master problem
if res then
forall(p in ProdMach) solstart(p):= getsol(start(p))
if MODE=2 then
initializations to "rmt:sol_"+M+".dat"
solstart as "sol"
end-initializations
end-if
send(EVENT_SOLVED,0)
else
send(EVENT_FAILED,0)
end-if
! Update total running time measurement
initializations from "rmt:time_"+M+".dat"
solvetime
end-initializations
solvetime+= gettime-startsolve
initializations to "rmt:time_"+M+".dat"
solvetime
end-initializations
end-model
|
|
| sched_mainm.mos |
(!****************************************************************
Mosel example problems
======================
file sched_mainm.mos
````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
Combined MIP-MIP problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, March 2005, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + MIP) master problem"
uses "mmsystem", "mmxprs", "mmjobs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 1
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of operations (products)
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totSeq: real
ctrun: integer
Seqmodel: Model ! Reference to the sequencing model
ev: Event ! Event
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
! **** Problem definition ****
define_MIP_model ! Definition of the MIP model
res:=compile("sched_subm.mos") ! Compile the sequencing model
load(Seqmodel, "sched_subm.bim") ! Load the sequencing model
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
initializations to "raw:"
totsolve as "shmem:solvetime"
REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
initializations from "raw:"
totsolve as "shmem:solvetime"
end-initializations
writeln("Total submodel solve time: ", totsolve)
writeln("Total submodel time: ", totSeq)
writeln("Submodel runs: ", ctrun)
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
! forall(p in PRODS) sum(m in MACH) m*use(p,m) is_sos1
! SOS: more nodes, more subproblems to solve
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve (expensive in
! getsol)
! setparam("XPRS_PRESOLVEOPS", 2270) ! Slower than disabling presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
! setparam("XPRS_LOADNAMES", true)
setparam("XPRS_COLORDER", 2)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -200)
end-do
2: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
3: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
function solve_seq_problem(m: integer, ProdMach: set of integer, mode: integer): boolean
declarations
DURm: dynamic array(range) of integer
sol: dynamic array(range) of integer
solvetime: real
end-declarations
! Data for sequencing model
forall(p in ProdMach) DURm(p):= DUR(p,m)
initializations to "raw:"
ProdMach as "shmem:ProdMach"
DURm as "shmem:DURm"
end-initializations
! Solve the problem and retrieve the solution if it is feasible
startsolve:= gettime
returned:= false
if(getstatus(Seqmodel)=RT_RUNNING) then
fflush
writeln("Seqmodel is running")
fflush
exit(1)
end-if
ctrun+=1
run(Seqmodel, "NP=" + NP + ",VERBOSE=" + VERBOSE + ",MODE=" + mode)
wait ! Wait for a message from the submodel
ev:= getnextevent ! Retrieve the event
if getclass(ev)=EVENT_SOLVED then
returned:= true
if mode = 2 then
initializations from "raw:"
sol as "shmem:solstart"
end-initializations
forall(p in ProdMach) solstart(p):=sol(p)
end-if
elif getclass(ev)<>EVENT_FAILED then
writeln("Problem with Kalis")
exit(2)
end-if
wait
dropnextevent ! Ignore "submodel finished" event
totSeq+= (gettime-startsolve)
end-function
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer, ProdMach: set of integer)
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
ProdMach:={}
break
elif val>0.5 then
ProdMach+={p}
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Generate a cut for machine m if the sequencing subproblem is infeasible
function generate_cut_machine(m: integer): boolean
declarations
ProdMach: set of integer
end-declarations
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
! Solve the sequencing problem: if solved, save the solution,
! otherwise add an infeasibility cut to the MIP problem
size:= getsize(ProdMach)
returned:= false
if (size>1) then
if not solve_seq_problem(m, ProdMach, 1) then
Cut:= sum(p in ProdMach) use(p,m) - (size-1)
if VERBOSE > 2 then
writeln(m,": ", ProdMach, " <= ", size-1)
end-if
addcut(1, CT_LEQ, Cut)
returned:= true
end-if
end-if
end-function
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
returned:=false; ctcutold:=ctcut
forall(m in MACH) do
if generate_cut_machine(m) then
returned:=true ! Call this function again for this node
ctcut+=1
end-if
end-do
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
ProdMach: set of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
forall(m in MACH) do
ProdMach:= {}
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
Size:= getsize(ProdMach)
if Size > 1 then
! (Re)solve the sequencing problem
if not solve_seq_problem(m, ProdMach, 2) then
writeln("Something wrong here: ", m, ProdMach)
end-if
elif Size=1 then
elem:=min(p in ProdMach) p
solstart(elem):=REL(elem)
end-if
end-do
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_subm.mos |
(!****************************************************************
Mosel example problems
======================
file sched_subm.mos
```````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
MIP branch-and-cut problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
*** Not intended to be run standalone - run from sched_mainm.mos ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, June 2005
*****************************************************************!)
model "Schedule (MIP+MIP) MIP subproblem"
uses "mmxprs", "mmjobs" , "mmsystem"
parameters
VERBOSE = 1
NP = 12 ! Number of products
MODE = 1 ! 1 - decide feasibility
! 2 - return complete solution
end-parameters
startsolve:= gettime
declarations
PRODS = 1..NP ! Set of products
ProdMach: set of integer
end-declarations
initializations from "raw:"
ProdMach as "shmem:ProdMach"
end-initializations
finalize(ProdMach)
NJ:= getsize(ProdMach)
declarations
RANKS=1..NJ ! Task positions
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
DURm: array(ProdMach) of integer ! Processing times on machine m
solstart: array(ProdMach) of integer ! Solution values for start times
rank: array(ProdMach,RANKS) of mpvar ! =1 if task p at position k
start: array(RANKS) of mpvar ! Start time of task at position k
comp: array(RANKS) of mpvar ! Completion time of task at pos. k
finish: mpvar ! Total completion time
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
solvetime: real
end-declarations
initializations from "raw:"
DURm as "shmem:DURm" REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
! One task per position
forall(k in RANKS) sum(p in ProdMach) rank(p,k) = 1
! One position per job
forall(p in ProdMach) sum(k in RANKS) rank(p,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
start(k+1) >= start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Start times
forall(k in RANKS) start(k) >= sum(p in ProdMach) REL(p)*rank(p,k)
! Completion times
forall(k in RANKS) comp(k) = start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Due dates
forall(k in RANKS) comp(k) <= sum(p in ProdMach) DUE(p)*rank(p,k)
forall(p in ProdMach,k in RANKS) rank(p,k) is_binary
! Objective function: minimize latest completion time
forall(k in RANKS) finish >= comp(k)
! if MODE=1 then
setparam("XPRS_MAXMIPSOL", 1) ! Stop at first feasible solution
! end-if
minimize(finish)
res:= getparam("XPRS_MIPSTATUS")
! Pass solution to master problem
if (res=XPRS_MIP_SOLUTION or res=XPRS_MIP_OPTIMAL) then
forall(p in ProdMach)
solstart(p):=
round(getsol(start( round(getsol(sum(k in RANKS) k*rank(p,k))) )))
if MODE=2 then
initializations to "raw:"
solstart as "shmem:solstart"
end-initializations
end-if
send(EVENT_SOLVED,0)
else
send(EVENT_FAILED,0)
end-if
! Update total running time measurement
initializations from "raw:"
solvetime as "shmem:solvetime"
end-initializations
solvetime+= gettime-startsolve
initializations to "raw:"
solvetime as "shmem:solvetime"
end-initializations
end-model
|
|
| sched_mainmp.mos |
(!****************************************************************
Mosel example problems
======================
file sched_mainmp.mos
`````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of subproblems --
Combined MIP-MIP problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
*** ATTENTION: This model will not run properly if no ***
*** sufficient number of Xpress licences is available. ***
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Aug. 2005, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + MIP) master problem"
uses "mmsystem", "mmxprs", "mmjobs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 1
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of operations (products)
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer
OpMach: array(MACH,PRODS) of integer ! Tasks assigned to machines
NumOp: array(MACH) of integer ! Number of tasks assigned to mach.s
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totSeq,solveM: real ! Time measurement
ctrun: integer ! Iteration counter (subproblems)
Seqmodel: array(MACH) of Model ! References to the sequencing models
ev: Event ! Event
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
! **** Problem definition ****
define_MIP_model ! Definition of the MIP model
res:=compile("sched_submp.mos") ! Compile the sequencing model
forall(m in MACH) do
load(Seqmodel(m), "sched_submp.bim") ! Load the sequencing models
Seqmodel(m).uid:= m ! Store the model indices as UID
end-do
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
forall (m in MACH)
initializations to "raw:"
totsolve as "shmem:solvetime"+m
end-initializations
initializations to "raw:"
REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
forall (m in MACH) do
initializations from "raw:"
solveM as "shmem:solvetime"+m
end-initializations
totsolve += solveM
end-do
writeln("Total submodel solve time: ", totsolve)
writeln("Total submodel time: ", totSeq)
writeln("Submodel runs: ", ctrun)
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
! forall(p in PRODS) sum(m in MACH) m*use(p,m) is_sos1
! SOS: more nodes, more subproblems to solve
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve (expensive in
! getsol)
! setparam("XPRS_PRESOLVEOPS", 2270) ! Slower than disabling presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
! setparam("XPRS_LOADNAMES", true)
setparam("XPRS_COLORDER", 2)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -200)
end-do
2: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
3: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
procedure start_seq_problem(m: integer, mode: integer)
declarations
ProdMach: set of integer
DURm: dynamic array(range) of integer
end-declarations
! Data for sequencing model
forall(p in 1..NumOp(m)) ProdMach+={OpMach(m,p)}
forall(p in ProdMach) DURm(p):= DUR(p,m)
initializations to "raw:"
ProdMach as "shmem:ProdMach"+m
DURm as "shmem:DUR"+m
end-initializations
! Solve the problem and retrieve the solution if it is feasible
returned:= false
if(getstatus(Seqmodel(m))=RT_RUNNING) then
fflush
writeln("Seqmodel is running")
fflush
exit(1)
end-if
ctrun+=1
run(Seqmodel(m), "NP=" + NP + ",VERBOSE=" + VERBOSE + ",MODE=" + mode +
",M=" + m)
end-procedure
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer)
NumOp(m):=0
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
NumOp(m):=0
break
elif val>0.5 then
NumOp(m)+=1
OpMach(m,NumOp(m)):= p
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Add a cut for machine m
procedure add_cut_machine(m: integer)
Cut:= sum(p in 1..NumOp(m)) use(OpMach(m,p),m) - (NumOp(m)-1)
if VERBOSE > 2 then
write(m,": ")
forall(p in 1..NumOp(m)) write(OpMach(m,p), " ")
writeln(" <= ", NumOp(m)-1)
end-if
addcut(1, CT_LEQ, Cut)
end-procedure
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
declarations
ToSolve: set of integer
end-declarations
returned:=false; ctcutold:=ctcut
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 0 then ToSolve += {m}; end-if
end-do
! Start solving the sequencing models
startsolve:= gettime
forall(m in ToSolve) start_seq_problem(m, 1)
! Retrieve all results/termination messages
if getsize(ToSolve) > 0 then
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: solved:=true ! Nothing to do
EVENT_FAILED: do
M:=ev.fromuid ! UID of model sending the event
add_cut_machine(M)
ctcut+=1
returned:=true ! Call cut gen. again for this node
end-do
else writeln("Problem with a subproblem")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
end-if
totSeq+= (gettime-startsolve)
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
sol: dynamic array(range) of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 1 then
ToSolve += {m}
elif NumOp(m) = 1 then
solstart(OpMach(m,1)):= REL(OpMach(m,1))
end-if
end-do
! Start solving the CP sequencing models
startsolve:= gettime
forall(m in ToSolve) start_seq_problem(m, 2)
! Retrieve all results/termination messages
ctend:= 0
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: do
M:= ev.fromuid ! UID of model sending the event
initializations from "raw:"
sol as "shmem:solstart"+M
end-initializations
forall(p in 1..NumOp(M))
solstart(OpMach(M,p)):=sol(OpMach(M,p))
end-do
EVENT_FAILED: do
M:= ev.fromuid ! UID of model sending the event
writeln("Something wrong here: ", M, OpMach, NumOp)
end-do
else writeln("Problem with subproblem solving")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_submp.mos |
(!****************************************************************
Mosel example problems
======================
file sched_submp.mos
````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of sequencing subproblems --
MIP branch-and-cut problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
*** Not intended to be run standalone - run from sched_mainmp.mos ***
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, Aug. 2005
*****************************************************************!)
model "Schedule (MIP+MIP) MIP subproblem"
uses "mmxprs", "mmjobs" , "mmsystem"
parameters
VERBOSE = 1
M = 1 ! Number of the machine
NP = 12 ! Number of products
MODE = 1 ! 1 - decide feasibility
! 2 - return complete solution
end-parameters
startsolve:= gettime
declarations
PRODS = 1..NP ! Set of products
ProdMach: set of integer
end-declarations
initializations from "raw:"
ProdMach as "shmem:ProdMach"+M
end-initializations
finalize(ProdMach)
NJ:= getsize(ProdMach)
declarations
RANKS=1..NJ ! Task positions
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
DURm: array(ProdMach) of integer ! Processing times on machine m
solstart: array(ProdMach) of integer ! Solution values for start times
rank: array(ProdMach,RANKS) of mpvar ! =1 if task p at position k
start: array(RANKS) of mpvar ! Start time of task at position k
comp: array(RANKS) of mpvar ! Completion time of task at pos. k
finish: mpvar ! Total completion time
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
solvetime: real
end-declarations
initializations from "raw:"
DURm as "shmem:DUR"+M REL as "shmem:REL" DUE as "shmem:DUE"
end-initializations
! One task per position
forall(k in RANKS) sum(p in ProdMach) rank(p,k) = 1
! One position per job
forall(p in ProdMach) sum(k in RANKS) rank(p,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
start(k+1) >= start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Start times
forall(k in RANKS) start(k) >= sum(p in ProdMach) REL(p)*rank(p,k)
! Completion times
forall(k in RANKS) comp(k) = start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Due dates
forall(k in RANKS) comp(k) <= sum(p in ProdMach) DUE(p)*rank(p,k)
forall(p in ProdMach,k in RANKS) rank(p,k) is_binary
! Objective function: minimize latest completion time
forall(k in RANKS) finish >= comp(k)
! if MODE=1 then
setparam("XPRS_MAXMIPSOL", 1) ! Stop at first feasible solution
! end-if
minimize(finish)
res:= getparam("XPRS_MIPSTATUS")
! Pass solution to master problem
if (res=XPRS_MIP_SOLUTION or res=XPRS_MIP_OPTIMAL) then
forall(p in ProdMach)
solstart(p):=
round(getsol(start( round(getsol(sum(k in RANKS) k*rank(p,k))) )))
if MODE=2 then
initializations to "raw:"
solstart as "shmem:solstart"+M
end-initializations
end-if
send(EVENT_SOLVED,0)
else
send(EVENT_FAILED,0)
end-if
! Update total running time measurement
initializations from "raw:"
solvetime as "shmem:solvetime"+M
end-initializations
solvetime+= gettime-startsolve
initializations to "raw:"
solvetime as "shmem:solvetime"+M
end-initializations
end-model
|
|
| sched_mainmpd.mos |
(!****************************************************************
Mosel example problems
======================
file sched_mainmpd.mos
``````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of subproblems --
-- Distributed computing version --
Combined MIP-MIP problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
Before running this model, you need to set up the list
NODES with machine names/addresses of your local network.
All nodes that are used need to have the same version of
Xpress installed and suitably licensed, and the server
"xprmsrv" must have been started on these machines.
All files are local to the root node, no write access is
required at remote nodes.
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + MIP) master problem"
uses "mmsystem", "mmxprs", "mmjobs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 1
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of operations (products)
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer
OpMach: array(MACH,PRODS) of integer ! Tasks assigned to machines
NumOp: array(MACH) of integer ! Number of tasks assigned to mach.s
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totSeq,solveM: real ! Time measurement
ctrun: integer ! Iteration counter (subproblems)
Seqmodel: array(MACH) of Model ! References to the sequencing models
ev: Event ! Event
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
NODES: list of string ! Set of available nodes
nodeInst: dynamic array(set of string) of Mosel ! Mosel instances on remote nodes
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
!**** Setting up remote Mosel instances ****
sethostalias("localhost","rcmd:")
NODES:= ["","localhost"]
!!! This list must have at least 1 element.
!!! Use machine names within your local network, IP addresses, or
!!! empty string for the current node running this model.
forall(n in NODES, nct as counter) do
create(nodeInst(n))
if connect(nodeInst(n), n)<>0 then exit(1); end-if
if nct>= NM then break; end-if ! Stop when started enough
end-do
! **** Problem definition ****
define_MIP_model ! Definition of the MIP model
res:=compile("sched_submpd.mos") ! Compile the sequencing model
if res<>0 then exit(2); end-if
ct:=0
forall(m in MACH) do
ct:= if(ct<NODES.size, ct+1, 1) ! Get next node in list or restart
n:= getlast(gethead(NODES,ct)) ! from beginning when end is reached
load(nodeInst(n), Seqmodel(m), "rmt:sched_submpd.bim")
! Load the sequencing models
Seqmodel(m).uid:= m ! Store the model indices
end-do
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
forall (m in MACH)
initializations to "time_"+m+".dat"
totsolve as "solvetime"
end-initializations
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
forall (m in MACH) do
initializations from "time_"+m+".dat"
solveM as "solvetime"
end-initializations
totsolve += solveM
end-do
writeln("Total submodel solve time: ", totsolve)
writeln("Total submodel time: ", totSeq)
writeln("Submodel runs: ", ctrun)
fdelete("sched_submpd.bim") ! Cleaning up
forall(m in MACH) fdelete("sol_"+m+".dat")
forall(m in MACH) fdelete("sol_"+m+".dat~")
forall(m in MACH) fdelete("time_"+m+".dat")
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
! forall(p in PRODS) sum(m in MACH) m*use(p,m) is_sos1
! SOS: more nodes, more subproblems to solve
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve (expensive in
! getsol)
! setparam("XPRS_PRESOLVEOPS", 2270) ! Slower than disabling presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
! setparam("XPRS_LOADNAMES", true)
setparam("XPRS_COLORDER", 2)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -200)
end-do
2: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
3: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
procedure start_seq_problem(m: integer, mode: integer)
declarations
ProdMach: set of integer
DURm: dynamic array(range) of integer
end-declarations
! Data for sequencing model
forall(p in 1..NumOp(m)) ProdMach+={OpMach(m,p)}
forall(p in ProdMach) DURm(p):= DUR(p,m)
initializations to "sol_"+m+".dat"
ProdMach
DURm
end-initializations
! Solve the problem and retrieve the solution if it is feasible
returned:= false
if(getstatus(Seqmodel(m))=RT_RUNNING) then
fflush
writeln("Seqmodel is running")
fflush
exit(1)
end-if
ctrun+=1
run(Seqmodel(m), "NP=" + NP + ",VERBOSE=" + VERBOSE + ",MODE=" + mode +
",M=" + m + ",DATAFILE=" + DATAFILE)
end-procedure
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer)
NumOp(m):=0
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
NumOp(m):=0
break
elif val>0.5 then
NumOp(m)+=1
OpMach(m,NumOp(m)):= p
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Add a cut for machine m
procedure add_cut_machine(m: integer)
Cut:= sum(p in 1..NumOp(m)) use(OpMach(m,p),m) - (NumOp(m)-1)
if VERBOSE > 2 then
write(m,": ")
forall(p in 1..NumOp(m)) write(OpMach(m,p), " ")
writeln(" <= ", NumOp(m)-1)
end-if
addcut(1, CT_LEQ, Cut)
end-procedure
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
declarations
ToSolve: set of integer
end-declarations
returned:=false; ctcutold:=ctcut
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 0 then ToSolve += {m}; end-if
end-do
! Start solving the sequencing models
startsolve:= gettime
forall(m in ToSolve) start_seq_problem(m, 1)
! Retrieve all results/termination messages
if getsize(ToSolve) > 0 then
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: solved:=true ! Nothing to do
EVENT_FAILED: do
M:=ev.fromuid ! ID of model sending the event
add_cut_machine(M)
ctcut+=1
returned:=true ! Call cut gen. again for this node
end-do
else writeln("Problem with a subproblem")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
end-if
totSeq+= (gettime-startsolve)
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
sol: dynamic array(range) of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
! Collect the operations assigned to machines
forall(m in MACH) do
products_on_machine(m)
if NumOp(m) > 1 then
ToSolve += {m}
elif NumOp(m) = 1 then
solstart(OpMach(m,1)):= REL(OpMach(m,1))
end-if
end-do
! Start solving the CP sequencing models
startsolve:= gettime
forall(m in ToSolve) start_seq_problem(m, 2)
! Retrieve all results/termination messages
ctend:= 0
repeat
wait ! Wait for the next event
ev:= getnextevent ! Get the event
case getclass(ev) of ! Get the event class
EVENT_END: ctend+=1 ! Submodel run terminated
EVENT_SOLVED: do
M:=ev.fromuid ! UID of model sending the event
initializations from "sol_"+M+".dat"
sol
end-initializations
fdelete("sol_"+M+".dat")
forall(p in 1..NumOp(M))
solstart(OpMach(M,p)):=sol(OpMach(M,p))
end-do
EVENT_FAILED: do
M:=ev.fromuid ! UID of model sending the event
writeln("Something wrong here: ", M, OpMach, NumOp)
end-do
else writeln("Problem with subproblem solving")
exit(2)
end-case
until ctend=getsize(ToSolve) ! All models have finished
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_submpd.mos |
(!****************************************************************
Mosel example problems
======================
file sched_submpd.mos
`````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
-- Parallel solving of sequencing subproblems --
-- Distributed computing version --
MIP branch-and-cut problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
*** Not intended to be run standalone - run from sched_mainmpd.mos ***
(c) 2010 Fair Isaac Corporation
author: S. Heipcke, May 2010
*****************************************************************!)
model "Schedule (MIP+MIP) MIP subproblem"
uses "mmxprs", "mmjobs" , "mmsystem"
parameters
DATAFILE = "sched_3_12.dat"
VERBOSE = 1
M = 1 ! Number of the machine
NP = 12 ! Number of products
MODE = 1 ! 1 - decide feasibility
! 2 - return complete solution
end-parameters
startsolve:= gettime
declarations
PRODS = 1..NP ! Set of products
ProdMach: set of integer
end-declarations
initializations from "rmt:sol_"+M+".dat"
ProdMach
end-initializations
finalize(ProdMach)
NJ:= getsize(ProdMach)
declarations
RANKS=1..NJ ! Task positions
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
DURm: array(ProdMach) of integer ! Processing times on machine m
solstart: array(ProdMach) of integer ! Solution values for start times
rank: array(ProdMach,RANKS) of mpvar ! =1 if task p at position k
start: array(RANKS) of mpvar ! Start time of task at position k
comp: array(RANKS) of mpvar ! Completion time of task at pos. k
finish: mpvar ! Total completion time
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
solvetime: real
end-declarations
initializations from "rmt:sol_"+M+".dat"
DURm
end-initializations
initializations from "rmt:"+DATAFILE
REL DUE
end-initializations
! One task per position
forall(k in RANKS) sum(p in ProdMach) rank(p,k) = 1
! One position per job
forall(p in ProdMach) sum(k in RANKS) rank(p,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
start(k+1) >= start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Start times
forall(k in RANKS) start(k) >= sum(p in ProdMach) REL(p)*rank(p,k)
! Completion times
forall(k in RANKS) comp(k) = start(k) + sum(p in ProdMach) DURm(p)*rank(p,k)
! Due dates
forall(k in RANKS) comp(k) <= sum(p in ProdMach) DUE(p)*rank(p,k)
forall(p in ProdMach,k in RANKS) rank(p,k) is_binary
! Objective function: minimize latest completion time
forall(k in RANKS) finish >= comp(k)
! if MODE=1 then
setparam("XPRS_MAXMIPSOL", 1) ! Stop at first feasible solution
! end-if
minimize(finish)
res:= getparam("XPRS_MIPSTATUS")
! Pass solution to master problem
if (res=XPRS_MIP_SOLUTION or res=XPRS_MIP_OPTIMAL) then
forall(p in ProdMach)
solstart(p):=
round(getsol(start( round(getsol(sum(k in RANKS) k*rank(p,k))) )))
if MODE=2 then
initializations to "rmt:sol_"+M+".dat"
solstart as "sol"
end-initializations
end-if
send(EVENT_SOLVED,0)
else
send(EVENT_FAILED,0)
end-if
! Update total running time measurement
initializations from "rmt:time_"+M+".dat"
solvetime
end-initializations
solvetime+= gettime-startsolve
initializations to "rmt:time_"+M+".dat"
solvetime
end-initializations
end-model
|
|
| sched_singlem.mos |
(!****************************************************************
Mosel example problems
======================
file sched_singlem.mos
``````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
Combined MIP-MIP problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
- Definition of multiple problems within a single model file. -
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2009 Fair Isaac Corporation
author: S. Heipcke, Jan. 2009, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + MIP) problem"
uses "mmsystem", "mmxprs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 0
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of operations (products)
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totSeq: real
ctrun: integer
EVENT_SOLVED=2 ! Event codes sent by submodels
EVENT_FAILED=3
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
! **** Problem definition ****
define_MIP_model ! Definition of the main MIP model
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
writeln("Total submodel solve time: ", totsolve)
writeln("Total submodel time: ", totSeq)
writeln("Submodel runs: ", ctrun)
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
! forall(p in PRODS) sum(m in MACH) m*use(p,m) is_sos1
! SOS: more nodes, more subproblems to solve
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve (expensive in
! getsol)
! setparam("XPRS_PRESOLVEOPS", 2270) ! Slower than disabling presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
! setparam("XPRS_LOADNAMES", true)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -200)
end-do
2: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
3: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
function solve_seq_problem(m: integer, PMach: set of integer, mode: integer): boolean
returned:= false
ProdMach:= PMach
finalize(ProdMach)
NJ:= getsize(ProdMach)
startsubm:= gettime
ctrun+=1
with mpproblem do
declarations
RANKS=1..NJ ! Task positions
rank: array(ProdMach,RANKS) of mpvar ! =1 if task p at position k
start: array(RANKS) of mpvar ! Start time of task at position k
comp: array(RANKS) of mpvar ! Completion time of task at pos. k
finish: mpvar ! Total completion time
end-declarations
! Solve the problem and retrieve the solution if it is feasible
! One task per position
forall(k in RANKS) sum(p in ProdMach) rank(p,k) = 1
! One position per job
forall(p in ProdMach) sum(k in RANKS) rank(p,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
start(k+1) >= start(k) + sum(p in ProdMach) DUR(p,m)*rank(p,k)
! Start times
forall(k in RANKS) start(k) >= sum(p in ProdMach) REL(p)*rank(p,k)
! Completion times
forall(k in RANKS) comp(k) = start(k) + sum(p in ProdMach) DUR(p,m)*rank(p,k)
! Due dates
forall(k in RANKS) comp(k) <= sum(p in ProdMach) DUE(p)*rank(p,k)
forall(p in ProdMach,k in RANKS) rank(p,k) is_binary
! Objective function: minimize latest completion time
forall(k in RANKS) finish >= comp(k)
setparam("XPRS_MAXMIPSOL", 1) ! Stop at first feasible solution
if VERBOSE<4 then ! Verbosity setting is inherited: need to reset it
setparam("XPRS_VERBOSE", false)
else
setparam("XPRS_VERBOSE", true)
end-if
startsolve:= gettime
minimize(finish)
res:= getparam("XPRS_MIPSTATUS")
! Pass solution to master problem
if (res=XPRS_MIP_SOLUTION or res=XPRS_MIP_OPTIMAL) then
returned:= true
if mode=2 then
forall(p in ProdMach)
solstart(p):=
round(getsol(start( round(getsol(sum(k in RANKS) k*rank(p,k))) )))
end-if
elif getprobstat<>XPRS_INF then
writeln("Problem with solving subproblem")
exit(2)
end-if
end-do
totsolve+= (gettime-startsolve)
totSeq+= (gettime-startsubm)
end-function
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer, ProdMach: set of integer)
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
ProdMach:={}
break
elif val>0.5 then
ProdMach+={p}
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Generate a cut for machine m if the sequencing subproblem is infeasible
function generate_cut_machine(m: integer): boolean
declarations
ProdMach: set of integer
end-declarations
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
! Solve the sequencing problem: if solved, save the solution,
! otherwise add an infeasibility cut to the MIP problem
size:= getsize(ProdMach)
returned:= false
if (size>1) then
if not solve_seq_problem(m, ProdMach, 1) then
Cut:= sum(p in ProdMach) use(p,m) - (size-1)
if VERBOSE > 2 then
writeln(m,": ", ProdMach, " <= ", size-1)
end-if
addcut(1, CT_LEQ, Cut)
returned:= true
end-if
end-if
end-function
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
returned:=false; ctcutold:=ctcut
(!
forall(m in MACH) do
forall(p in PRODS) write(getsol(use(p,m)), " ")
writeln
end-do
if getparam("XPRS_NODES")=2 then
command("writesol 'solms" + getparam("XPRS_NODES") + "out.txt'")
end-if
!)
forall(m in MACH) do
if generate_cut_machine(m) then
returned:=true ! Call this function again for this node
ctcut+=1
end-if
end-do
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
ProdMach: set of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
forall(m in MACH) do
ProdMach:= {}
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
Size:= getsize(ProdMach)
if Size > 1 then
! (Re)solve the sequencing problem
if not solve_seq_problem(m, ProdMach, 2) then
writeln("Something wrong here: ", m, ProdMach)
end-if
elif Size=1 then
elem:=min(p in ProdMach) p
solstart(elem):=REL(elem)
end-if
end-do
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_singlema.mos |
(!****************************************************************
Mosel example problems
======================
file sched_singlema.mos
```````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
Combined MIP-MIP problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
- Definition of multiple problems within a single model file. -
- Subproblem decision variables + ctr declared globally:
faster than sched_singlem.mos and sched_singlemg.mos -
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2009 Fair Isaac Corporation
author: S. Heipcke, Jan. 2009, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + MIP) problem"
uses "mmsystem", "mmxprs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 0
end-parameters
forward procedure define_MIP_model
forward procedure define_seq_problem
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of operations (products)
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totSeq: real
ctrun: integer
rank: array(PRODS,PRODS) of mpvar ! =1 if task p at position k
start: array(PRODS) of mpvar ! Start time of task at position k
comp: array(PRODS) of mpvar ! Completion time of task at pos. k
finish: mpvar ! Total completion time
seqprob: mpproblem
OneTask, OnePos, JobSeq, CalcStart, CalcEnd, CalcDue, LimFin: array(PRODS) of linctr
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
! **** Problem definition ****
define_MIP_model ! Definition of the main MIP model
define_seq_problem ! Definitions for sequencing subprob.
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
writeln("Total submodel solve time: ", totsolve)
writeln("Total submodel time: ", totSeq)
writeln("Submodel runs: ", ctrun)
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
! forall(p in PRODS) sum(m in MACH) m*use(p,m) is_sos1
! SOS: more nodes, more subproblems to solve
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve (expensive in
! getsol)
! setparam("XPRS_PRESOLVEOPS", 2270) ! Slower than disabling presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
! setparam("XPRS_LOADNAMES", true)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -200)
end-do
2: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
3: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Global definitions for the sequencing problem
procedure define_seq_problem
with seqprob do
forall(p,k in PRODS) CtrBin(p,k):=rank(p,k) is_binary
end-do
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
function solve_seq_problem(m: integer, PMach: set of integer, mode: integer): boolean
returned:= false
ProdMach:= PMach
finalize(ProdMach)
NJ:= getsize(ProdMach)
RANKS:=1..NJ ! Task positions
startsubm:= gettime
ctrun+=1
with seqprob do
! Solve the problem and retrieve the solution if it is feasible
! One task per position
forall(k in RANKS) OneTask(k):= sum(p in ProdMach) rank(p,k) = 1
! One position per job
forall(p in ProdMach) OnePos(p):= sum(k in RANKS) rank(p,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
JobSeq(k):= start(k+1) >= start(k) + sum(p in ProdMach) DUR(p,m)*rank(p,k)
! Start times
forall(k in RANKS) CalcStart(k):= start(k) >= sum(p in ProdMach) REL(p)*rank(p,k)
! Completion times
forall(k in RANKS) CalcEnd(k):= comp(k) = start(k) + sum(p in ProdMach) DUR(p,m)*rank(p,k)
! Due dates
forall(k in RANKS) CalcDue(k):= comp(k) <= sum(p in ProdMach) DUE(p)*rank(p,k)
! forall(p in ProdMach,k in RANKS) CtrBin(p,k):=rank(p,k) is_binary
! Objective function: minimize latest completion time
forall(k in RANKS) LimFin(k):= finish >= comp(k)
setparam("XPRS_MAXMIPSOL", 1) ! Stop at first feasible solution
if VERBOSE<4 then ! Verbosity setting is inherited: need to reset it
setparam("XPRS_VERBOSE", false)
else
setparam("XPRS_VERBOSE", true)
end-if
startsolve:= gettime
minimize(finish)
res:= getparam("XPRS_MIPSTATUS")
! Pass solution to master problem
if (res=XPRS_MIP_SOLUTION or res=XPRS_MIP_OPTIMAL) then
returned:= true
if mode=2 then
forall(p in ProdMach)
solstart(p):=
round(getsol(start( round(getsol(sum(k in RANKS) k*rank(p,k))) )))
end-if
elif getprobstat<>XPRS_INF then
writeln("Problem with solving subproblem")
exit(2)
end-if
! Reset subproblem
forall(k in RANKS) OneTask(k):= 0
forall(p in ProdMach) OnePos(p):= 0
forall(k in 1..NJ-1) JobSeq(k):= 0
forall(k in RANKS) CalcStart(k):= 0
forall(k in RANKS) CalcEnd(k):= 0
forall(k in RANKS) CalcDue(k):= 0
forall(k in RANKS) LimFin(k):= 0
end-do
totsolve+= (gettime-startsolve)
totSeq+= (gettime-startsubm)
end-function
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer, ProdMach: set of integer)
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
ProdMach:={}
break
elif val>0.5 then
ProdMach+={p}
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Generate a cut for machine m if the sequencing subproblem is infeasible
function generate_cut_machine(m: integer): boolean
declarations
ProdMach: set of integer
end-declarations
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
! Solve the sequencing problem: if solved, save the solution,
! otherwise add an infeasibility cut to the MIP problem
size:= getsize(ProdMach)
returned:= false
if (size>1) then
if not solve_seq_problem(m, ProdMach, 1) then
Cut:= sum(p in ProdMach) use(p,m) - (size-1)
if VERBOSE > 2 then
writeln(m,": ", ProdMach, " <= ", size-1)
end-if
addcut(1, CT_LEQ, Cut)
returned:= true
end-if
end-if
end-function
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
returned:=false; ctcutold:=ctcut
forall(m in MACH) do
if generate_cut_machine(m) then
returned:=true ! Call this function again for this node
ctcut+=1
end-if
end-do
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
ProdMach: set of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
forall(m in MACH) do
ProdMach:= {}
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
Size:= getsize(ProdMach)
if Size > 1 then
! (Re)solve the sequencing problem
if not solve_seq_problem(m, ProdMach, 2) then
writeln("Something wrong here: ", m, ProdMach)
end-if
elif Size=1 then
elem:=min(p in ProdMach) p
solstart(elem):=REL(elem)
end-if
end-do
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
| sched_singlemg.mos |
(!****************************************************************
Mosel example problems
======================
file sched_singlemg.mos
```````````````````````
Scheduling with resource dependent durations and cost, subject
to given release dates and due dates.
Combined MIP-MIP problem solving: cut generation for MIP model
by solving MIP subproblems at nodes in the MIP branching tree.
- Definition of multiple problems within a single model file. -
- Subproblem decision variables + ctr declared globally:
faster than sched_singlem.mos -
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2009 Fair Isaac Corporation
author: S. Heipcke, Jan. 2009, rev. Nov. 2019
*****************************************************************!)
model "Schedule (MIP + MIP) problem"
uses "mmsystem", "mmxprs"
parameters
DATAFILE = "Data/sched_3_12.dat"
VERBOSE = 0
end-parameters
forward procedure define_MIP_model
forward procedure setup_cutmanager
forward public function generate_cuts: boolean
forward public procedure print_solution
declarations
NP: integer ! Number of operations (products)
NM: integer ! Number of machines
end-declarations
initializations from DATAFILE
NP NM
end-initializations
declarations
PRODS = 1..NP ! Set of products
MACH = 1..NM ! Set of machines
REL: array(PRODS) of integer ! Release dates of orders
DUE: array(PRODS) of integer ! Due dates of orders
MAX_LOAD: integer ! max_p DUE(p) - min_p REL(p)
COST: array(PRODS,MACH) of integer ! Processing cost of products
DUR: array(PRODS,MACH) of integer ! Processing times of products
starttime: real ! Measure program execution time
ctcut: integer ! Counter for cuts
solstart: array(PRODS) of integer
! **** MIP model:
use: array(PRODS,MACH) of mpvar ! 1 if p uses machine m, otherwise 0
Cost: linctr ! Objective function
totsolve,totSeq: real
ctrun: integer
rank: array(PRODS,PRODS) of mpvar ! =1 if task p at position k
start: array(PRODS) of mpvar ! Start time of task at position k
comp: array(PRODS) of mpvar ! Completion time of task at pos. k
finish: mpvar ! Total completion time
end-declarations
! Read data from file
initializations from DATAFILE
REL DUE COST DUR
end-initializations
! **** Problem definition ****
define_MIP_model ! Definition of the main MIP model
! **** Solution algorithm ****
starttime:= gettime
setup_cutmanager ! Settings for the MIP search
totsolve:= 0.0
minimize(Cost) ! Solve the problem
writeln("Number of cuts generated: ", ctcut)
writeln("(", gettime-starttime, "sec) Best solution value: ", getobjval)
writeln("Total submodel solve time: ", totsolve)
writeln("Total submodel time: ", totSeq)
writeln("Submodel runs: ", ctrun)
!-----------------------------------------------------------------
! Define the MIP model
procedure define_MIP_model
! Objective: total processing cost
Cost:= sum(p in PRODS, m in MACH) COST(p,m) * use(p,m)
! Each order needs exactly one machine for processing
forall(p in PRODS) sum(m in MACH) use(p,m) = 1
! Valid inequalities for strengthening the LP relaxation
MAX_LOAD:= max(p in PRODS) DUE(p) - min(p in PRODS) REL(p)
forall(m in MACH) sum(p in PRODS) DUR(p,m) * use(p,m) <= MAX_LOAD
forall(p in PRODS, m in MACH) use(p,m) is_binary
! forall(p in PRODS) sum(m in MACH) m*use(p,m) is_sos1
! SOS: more nodes, more subproblems to solve
end-procedure
!-----------------------------------------------------------------
! Xpress Optimizer settings for using the cut manager
procedure setup_cutmanager
setparam("XPRS_CUTSTRATEGY", 0) ! Disable automatic cuts
feastol:= getparam("XPRS_FEASTOL") ! Get Optimizer zero tolerance
setparam("zerotol", feastol * 10) ! Set comparison tolerance of Mosel
setparam("XPRS_PRESOLVE", 0) ! Disable presolve (expensive in
! getsol)
! setparam("XPRS_PRESOLVEOPS", 2270) ! Slower than disabling presolve
setparam("XPRS_MIPPRESOLVE", 0) ! Disable MIP presolve
command("KEEPARTIFICIALS=0") ! No global red. cost fixing
setparam("XPRS_SBBEST", 0) ! Turn strong branching off
setparam("XPRS_HEURSTRATEGY", 0) ! Disable MIP heuristics
setparam("XPRS_EXTRAROWS", 10000) ! Reserve space for cuts
setparam("XPRS_EXTRAELEMS", NP*30000) ! ... and cut coefficients
setcallback(XPRS_CB_CUTMGR, "generate_cuts") ! Define the cut mgr. callback
setcallback(XPRS_CB_INTSOL, "print_solution") ! Define the integer sol. cb.
! setparam("XPRS_LOADNAMES", true)
case VERBOSE of
1: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -200)
end-do
2: do
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", -100)
end-do
3: do ! Detailed MIP output
setparam("XPRS_VERBOSE", true)
setparam("XPRS_MIPLOG", 3)
end-do
end-case
end-procedure
!-----------------------------------------------------------------
! Define and solve the sequencing problem for one machine
function solve_seq_problem(m: integer, PMach: set of integer, mode: integer): boolean
returned:= false
ProdMach:= PMach
finalize(ProdMach)
NJ:= getsize(ProdMach)
RANKS:=1..NJ ! Task positions
startsubm:= gettime
ctrun+=1
with mpproblem do
! Solve the problem and retrieve the solution if it is feasible
! One task per position
forall(k in RANKS) OneTask(k):= sum(p in ProdMach) rank(p,k) = 1
! One position per job
forall(p in ProdMach) OnePos(p):= sum(k in RANKS) rank(p,k) = 1
! Sequence of jobs
forall(k in 1..NJ-1)
JobSeq(k):= start(k+1) >= start(k) + sum(p in ProdMach) DUR(p,m)*rank(p,k)
! Start times
forall(k in RANKS) CalcStart(k):= start(k) >= sum(p in ProdMach) REL(p)*rank(p,k)
! Completion times
forall(k in RANKS) CalcEnd(k):= comp(k) = start(k) + sum(p in ProdMach) DUR(p,m)*rank(p,k)
! Due dates
forall(k in RANKS) CalcDue(k):= comp(k) <= sum(p in ProdMach) DUE(p)*rank(p,k)
forall(p in ProdMach,k in RANKS) CtrBin(p,k):=rank(p,k) is_binary
! Objective function: minimize latest completion time
forall(k in RANKS) LimFin(k):= finish >= comp(k)
setparam("XPRS_MAXMIPSOL", 1) ! Stop at first feasible solution
if VERBOSE<4 then ! Verbosity setting is inherited: need to reset it
setparam("XPRS_VERBOSE", false)
else
setparam("XPRS_VERBOSE", true)
end-if
startsolve:= gettime
minimize(finish)
res:= getparam("XPRS_MIPSTATUS")
! Pass solution to master problem
if (res=XPRS_MIP_SOLUTION or res=XPRS_MIP_OPTIMAL) then
returned:= true
if mode=2 then
forall(p in ProdMach)
solstart(p):=
round(getsol(start( round(getsol(sum(k in RANKS) k*rank(p,k))) )))
end-if
elif getprobstat<>XPRS_INF then
writeln("Problem with solving subproblem")
exit(2)
end-if
end-do
totsolve+= (gettime-startsolve)
totSeq+= (gettime-startsubm)
end-function
!-----------------------------------------------------------------
! Collect the operations assigned to machine m
procedure products_on_machine(m: integer, ProdMach: set of integer)
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
ProdMach:={}
break
elif val>0.5 then
ProdMach+={p}
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Generate a cut for machine m if the sequencing subproblem is infeasible
function generate_cut_machine(m: integer): boolean
declarations
ProdMach: set of integer
end-declarations
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
! Solve the sequencing problem: if solved, save the solution,
! otherwise add an infeasibility cut to the MIP problem
size:= getsize(ProdMach)
returned:= false
if (size>1) then
if not solve_seq_problem(m, ProdMach, 1) then
Cut:= sum(p in ProdMach) use(p,m) - (size-1)
if VERBOSE > 2 then
writeln(m,": ", ProdMach, " <= ", size-1)
end-if
addcut(1, CT_LEQ, Cut)
returned:= true
end-if
end-if
end-function
!-----------------------------------------------------------------
! Cut generation callback function
public function generate_cuts: boolean
returned:=false; ctcutold:=ctcut
forall(m in MACH) do
if generate_cut_machine(m) then
returned:=true ! Call this function again for this node
ctcut+=1
end-if
end-do
if returned and VERBOSE>1 then
writeln("Node ", getparam("XPRS_NODES"), ": ", ctcut-ctcutold,
" cut(s) added")
end-if
end-function
!-----------------------------------------------------------------
! Solution callback function
public procedure print_solution
declarations
ProdMach: set of integer
end-declarations
writeln("(",gettime-starttime, "sec) Solution ",
getparam("XPRS_MIPSOLS"), ": Cost: ", getsol(Cost))
if VERBOSE > 1 then
forall(p in PRODS) do
forall(m in MACH) write(getsol(use(p,m))," ")
writeln
end-do
end-if
if VERBOSE > 0 then
forall(m in MACH) do
ProdMach:= {}
! Collect the operations assigned to machine m
products_on_machine(m, ProdMach)
Size:= getsize(ProdMach)
if Size > 1 then
! (Re)solve the sequencing problem
if not solve_seq_problem(m, ProdMach, 2) then
writeln("Something wrong here: ", m, ProdMach)
end-if
elif Size=1 then
elem:=min(p in ProdMach) p
solstart(elem):=REL(elem)
end-if
end-do
! Print out the result
forall(p in PRODS) do
msol:=sum(m in MACH) m*getsol(use(p,m))
writeln(p, " -> ", msol,": ", strfmt(solstart(p),2), " - ",
strfmt(DUR(p,round(msol))+solstart(p),2), " [",
REL(p), ", ", DUE(p), "]")
end-do
writeln("Time: ", gettime - starttime, "sec")
writeln
fflush
end-if
end-procedure
end-model
|
|
