(!****************************************************************
CP example problems
===================
file b1stadium_ka.mos
`````````````````````
Construction of a stadium
(See "Applications of optimization with Xpress-MP",
Section 7.1 Construction of a stadium)
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, March 2005, rev. Dec. 2010
*****************************************************************!)
model "B-1 Stadium construction (CP)"
uses "kalis"
declarations
N = 19 ! Number of tasks in the project
! (last = fictitious end task)
TASKS = 1..N
ARC: dynamic array(range,range) of integer ! Matrix of the adjacency graph
DUR: array(TASKS) of integer ! Duration of tasks
HORIZON : integer ! Time horizon
start: array(TASKS) of cpvar ! Start dates of tasks
bestend: integer
end-declarations
initializations from 'Data/b1stadium.dat'
DUR ARC
end-initializations
HORIZON:= sum(j in TASKS) DUR(j)
forall(j in TASKS) do
0 <= start(j); start(j) <= HORIZON
end-do
! Task i precedes task j
forall(i, j in TASKS | exists(ARC(i, j))) do
Prec(i,j):= start(i) + DUR(i) <= start(j)
if not cp_post(Prec(i,j)) then
writeln("Posting precedence ", i, "-", j, " failed")
exit(1)
end-if
end-do
! Since there are no side-constraints, the earliest possible completion
! time is the earliest start of the fictitiuous task N
bestend:= getlb(start(N))
start(N) <= bestend
writeln("Earliest possible completion time: ", bestend)
! For tasks on the critical path the start/completion times have been fixed
! by setting the bound on the last task. For all other tasks the range of
! possible start/completion times gets displayed.
forall(j in TASKS) writeln(j, ": ", start(j))
end-model
|
(!****************************************************************
CP example problems
===================
file b1stadium_main.mos
```````````````````````
Construction of a stadium
(See "Applications of optimization with Xpress-MP",
Section 7.1 Construction of a stadium)
1. Calculate the earliest completion time with the given
durations of the operations.
2. Reduce the completion time of the project such that the total
profit calculated as
BONUS_per_week_finished_earlier - COST_of_finishing_earlier
is maximized.
The first problem is solved merely by posting the precedence
constraints in a CP model. Since there are no side-constraints, the
earliest possible completion time is the earliest start of the last,
fictitiuous task N. We get it for free (i.e. without enumeration)
thanks to the propagation of constraints.
For the formulation of the second problem the definition of the
CP model is changed: durations are turned into variables and start
times are bounded by the previously calculated earliest completion
time. The feasible start time intervals are again determined by
constraint propagation.
The complete problem is then formulated and solved as an LP problem,
taking the lower bounds on start times from the CP model. Doing so
we may switch off the preprocessing of the LP model - the CP constraint
propagation is used as preprocessor.
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, March 2005, rev. Jul. 2017
*****************************************************************!)
model "B-1 Stadium construction (CP + LP) master model"
uses "mmxprs", "mmjobs"
forward procedure print_CP_solution(num: integer)
declarations
N = 19 ! Number of tasks in the project
! (last = fictitious end task)
TASKS = 1..N
ARC: dynamic array(range,range) of integer ! Matrix of the adjacency graph
DUR: array(TASKS) of integer ! Duration of tasks
BONUS: integer ! Bonus per week finished earlier
MAXW: array(TASKS) of integer ! Max. reduction of tasks (in weeks)
COST: array(TASKS) of real ! Cost of reducing tasks by a week
lbstart,ubstart: array(TASKS) of integer ! Bounds on start dates of tasks
HORIZON: integer ! Time horizon
bestend: integer ! CP solution value
CPmodel: Model ! Reference to the CP model
msg: Event ! Termination message sent by submodel
end-declarations
initializations from 'Data/b1stadium.dat'
DUR ARC MAXW BONUS COST
end-initializations
HORIZON:= sum(o in TASKS) DUR(o)
! **** First CP model ****
res:= compile("b1stadium_sub.mos") ! Compile the CP model
load(CPmodel, "b1stadium_sub.bim") ! Load the CP model
setworkdir(CPmodel, ".")
run(CPmodel, "MODE=1,HORIZON=" + HORIZON) ! Solve first version of CP model
wait ! Wait until subproblem finishes
msg:= getnextevent ! Get the termination event message
if getclass(msg)<>EVENT_END then ! Check message type
writeln("Submodel 1 is infeasible")
exit(1)
end-if
initializations from "raw:"
lbstart as "shmem:lbstart" ubstart as "shmem:ubstart"
end-initializations
bestend:= lbstart(N)
print_CP_solution(1)
! **** Second CP model ****
run(CPmodel, "MODE=2,HORIZON=" + bestend) ! Solve second version of CP model
wait ! Wait until subproblem finishes
msg:= getnextevent ! Get the termination event message
if getclass(msg)<>EVENT_END then ! Check message type
writeln("Submodel 2 is infeasible")
exit(2)
end-if
! Retrieve solution from memory
initializations from "raw:"
lbstart as "shmem:lbstart" ubstart as "shmem:ubstart"
end-initializations
print_CP_solution(2)
! **** LP model for second problem ****
declarations
start: array(TASKS) of mpvar ! Start times of tasks
save: array(TASKS) of mpvar ! Number of weeks finished early
end-declarations
! Objective function: total profit
Profit:= BONUS*save(N) - sum(i in 1..N-1) COST(i)*save(i)
! Precedence relations between tasks
forall(i,j in TASKS | exists(ARC(i,j)))
Precm(i,j):= start(i) + DUR(i) - save(i) <= start(j)
! Total duration
start(N) + save(N) = bestend
! Limit on number of weeks that may be saved
forall(i in 1..N-1) save(i) <= MAXW(i)
! Bounds on start times deduced by constraint propagation
forall(i in 1..N-1) do
lbstart(i) <= start(i); start(i) <= ubstart(i)
end-do
! Solve the second problem: maximize the total profit
setparam("XPRS_VERBOSE", true)
setparam("XPRS_PRESOLVE", 0) ! We use constraint propagation as preprocessor
maximize(Profit)
! Solution printing
writeln("Total profit: ", getsol(Profit))
writeln("Total duration: ", getsol(start(N)), " weeks")
forall(i in 1..N-1)
write(strfmt(i,2), ": ", strfmt(getsol(start(i)),-3),
if(i mod 6 = 0,"\n",""))
writeln
!*********************************************************************
procedure print_CP_solution(num: integer)
writeln("CP solution (version ", num, "):")
writeln("Earliest possible completion time: ", lbstart(N), " weeks")
forall(i in 1..N-1)
write(i, ": ", lbstart(i), if(lbstart(i)<ubstart(i), "-"+ubstart(i), ""),
if(i mod 6 = 0, "\n", ", "))
end-procedure
end-model
|
(!****************************************************************
CP example problems
===================
file b1stadium_sub.mos
``````````````````````
Construction of a stadium
(See "Applications of optimization with Xpress-MP",
Section 7.1 Construction of a stadium)
(c) 2008 Fair Isaac Corporation
author: S. Heipcke, March 2005, rev. Dec. 2010
*****************************************************************!)
model "B-1 Stadium construction (CP submodel)"
uses "kalis", "mmjobs"
parameters
MODE = 1 ! Model version: 1 - fixed durations
! 2 - variable dur.
HORIZON = 100 ! Time horizon
end-parameters
declarations
N = 19 ! Number of tasks in the project
! (last = fictitious end task)
TASKS = 1..N
ARC: dynamic array(range,range) of integer ! Matrix of the adjacency graph
DUR: array(TASKS) of integer ! Duration of tasks
MAXW: array(TASKS) of integer ! Max. reduction of tasks (in weeks)
start: array(TASKS) of cpvar ! Start dates of tasks
duration: array(TASKS) of cpvar ! Durations of tasks
lbstart,ubstart: array(TASKS) of integer ! Bounds on start dates of tasks
EVENT_FAILED=2 ! Event code sent by submodel
end-declarations
initializations from 'Data/b1stadium.dat'
DUR ARC
end-initializations
forall(j in TASKS) setdomain(start(j), 0, HORIZON)
if MODE = 1 then ! **** Fixed durations
! Precedence relations between tasks
forall(i, j in TASKS | exists(ARC(i, j))) do
Prec(i,j):= start(i) + DUR(i) <= start(j)
if not cp_post(Prec(i,j)) then
send(EVENT_FAILED,0)
end-if
end-do
! Earliest poss. completion time = earliest start of the fictitiuous task N
start(N) <= getlb(start(N))
else ! **** Durations are variables
initializations from 'Data/b1stadium.dat'
MAXW
end-initializations
forall(j in TASKS) setdomain(duration(j), DUR(j)-MAXW(j), DUR(j))
! Precedence relations between tasks
forall(i, j in TASKS | exists(ARC(i, j))) do
Prec(i,j):= start(i) + duration(i) <= start(j)
if not cp_post(Prec(i,j)) then
send(EVENT_FAILED,0)
end-if
end-do
end-if
! Pass solution data to the master model
forall(i in TASKS) do
lbstart(i):= getlb(start(i)); ubstart(i):= getub(start(i))
end-do
initializations to "raw:"
lbstart as "shmem:lbstart" ubstart as "shmem:ubstart"
end-initializations
end-model
|
