Implementation of question 2
The second problem can be solved with the following algorithm:
- Solve the CP problem for question 1 and retrieve the solution, in particular the earliest completion time bestend.
- Solve the CP problem for question 2 with the time horizon bestend and retrieve the start time intervals.
- Define and solve the LP model for the second problem, using the bounds on the start times from CP as bounds on the LP variables starti.
For the implementation, we would like to build on the CP model that we have shown above in the solution to question 1. However, since there is no means of modifying constraints that have been posted to the Kalis solver, we cannot simply work with a single file. Instead, we are going to split the implementation into two model files, one with the definition of the algorithms and the LP problem, and a second, the submodel, with the definition and solving of the CP problems. Depending on the model parameter MODE, the CP model either defines the model for question 1 or question 2. Instead of printing out an error message if an infeasibility is detected while posting the constraints, the CP model now sends a failure message to the master problem.
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
After compiling the CP submodel, the master model first runs the version for question 1, and retrieves the start time intervals. It then executes the CP submodel again, but now in the form for question 2 and with the time horizon bestend. The start time intervals from the solution of the second CP run are used in the subsequent definition of the LP problem.
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