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 start_i.

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.

       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

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