Using CP propagation as preprocessor

Topics covered in this section:

When the constraints in a CP model are posted to the solver, they often immediately trigger some reductions to the domains of the involved variables. In certain (easy) cases, it may even happen that the constraint propagation is sufficient to obtain a solution without having to start an enumeration.

The domain reductions obtained through the constraint propagation can be passed on to an LP or MIP model, thus replacing, or re-inforcing the preprocessing algorithms that are used by LP and MIP solvers.

The example description in the following sections is taken from Section 7.1 of the book `Applications of optimization with Xpress-MP'.

Project scheduling example

A town council wishes to construct a small stadium in order to improve the services provided to the people living in the district. After the invitation to tender, a local construction company is awarded the contract and wishes to complete the task within the shortest possible time. All the major tasks are listed in the following table. The durations are expressed in weeks. Some tasks can only start after the completion of certain other tasks. The last two columns of the table refer to question 2 which we shall see later.

**Table 1:** Data for stadium construction
Task	Description	Dur.	Prede- cessors	Max. reduct.	Add. cost per week (in 1000€)
1	Installing the construction site	2	none	0	–
2	Terracing	16	1	3	30
3	Constructing the foundations	9	2	1	26
4	Access roads and other networks	8	2	2	12
5	Erecting the basement	10	3	2	17
6	Main floor	6	4,5	1	15
7	Dividing up the changing rooms	2	4	1	8
8	Electrifying the terraces	2	6	0	–
9	Constructing the roof	9	4,6	2	42
10	Lighting of the stadium	5	4	1	21
11	Installing the terraces	3	6	1	18
12	Sealing the roof	2	9	0	–
13	Finishing the changing rooms	1	7	0	–
14	Constructing the ticket office	7	2	2	22
15	Secondary access roads	4	4,14	2	12
16	Means of signaling	3	8,11,14	1	6
17	Lawn and sport accessories	9	12	3	16
18	Handing over the building	1	17	0	–

Question 1: Which is the earliest possible date of completing the construction?

Question 2: The town council would like the project to terminate earlier than the time announced by the builder (answer to question 1). To obtain this, the council is prepared to pay a bonus of €30K for every week the work finishes early. The builder needs to employ additional workers and rent more equipment to cut down on the total time. In the preceding table he has summarized the maximum number of weeks he can save per task (column "Max. reduction") and the associated additional cost per week. When will the project be completed if the builder wishes to maximize his profit?

Model formulation for question 1

The representation of this classical project scheduling problem as a CP model is quite straightforward. We add a fictitious task with duration zero that corresponds to the end of the project. We thus consider the set of tasks TASKS = {1,...,N} where N is the fictitious end task. Let DUR_i be the duration of task i. The precedences between tasks are represented by a set of arcs, ARCS (an arc (i,j) ∈ ARCS symbolizes that task i precedes task j). The fictitious task follows all tasks that have no successor.

We define decision variables start_i for the start time of every task i. These variables take values within the interval {0,...,HORIZON} where HORIZON is the upper bound on the total duration given by the sum of all task durations.

We obtain the following simple CP model:

∀ i ∈ TASKS: start_i ∈ {0,..., HORIZON}
∀(i,j) ∈ ARCS: start_i + DUR_i ≤ start_j

Implementation of question 1

Since there are no side constraints, the earliest possible completion time is the earliest start of the fictitious task N. We can obtain this value without enumeration thanks to the propagation of constraints. After posting the precedence constraints we retrieve the earliest completion time bestend and set this value as the upper bound on the last task. This fixes the start and completion times for the tasks on the critical path; for all other tasks the start and completion times are reduced to the feasible intervals:

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

Results for question 1

The model in the previous section prints the following output. The earliest completion time is 64 weeks. For every operation (task), its start time or interval of possible start times is indicated.

Earliest possible completion time: 64
1: 0
2: 2
3: 18
4: [18..29]
5: 27
6: 37
7: [26..61]
8: [43..59]
9: 43
10: [26..59]
11: [43..58]
12: 52
13: [28..63]
14: [18..53]
15: [26..60]
16: [46..61]
17: 54
18: 63
19: 64

Model formulation for question 2

This second problem is called scheduling with project crashing. To reduce the total duration of the project, we need to take into account the result of the preceding optimization run, bestend. This value is now the upper bound on all start and completion time intervals.

Furthermore, for every task i let MAXW_i denote the maximum number of weeks by which the task may be shortened.

CP model

The durations of tasks are not fixed any more and are therefore now represented by decision variables duration_i that take values in the range {DUR_i - MAXW_i,..., DUR_i}.

With these additional variables the CP model now looks as follows:

∀ i ∈ TASKS: start_i ∈ {0,..., bestend}
∀ i ∈ TASKS: duration_i ∈ {DUR_i - MAXW_i,..., DUR_i}
∀(i,j) ∈ ARCS: start_i + duration_i ≤ start_j

This model does not include the objective function (i.e., maximization of the total gain from finishing the project early). This objective is dealt with by the LP model (see the following sections). As a result of the constraint propagation in the CP model, we merely obtain reduced start time intervals for the operations; the durations need to be determined either by enumeration or as shown below, by the LP solution algorithm.

LP model

We introduce variables start_i to represent the earliest start time of tasks i and variables save_i that correspond to the number of weeks that we wish to save for every task i. The only constraints that are given are the precedences. A task j may only start if all its predecessors have finished, which translates into the following constraints: if there is an arc between i and j, then the completion time of i (calculated as start_i + DUR_i - save_i) must not be larger than the start time of j.

∀ (i,j) ∈ ARCS: start_i + DUR_i - save_i ≤ start_j

The variables save_i are bounded by the maximum reduction in weeks, MAXW_i. These constraints must be satisfied for all tasks i except the last, fictitious task N.

∀ i ∈ TASKS \ {N}: save_i ≤ MAXW_i

For the last task, the variable save_N represents the number of weeks the project finishes earlier than the solution bestend calculated in answer to question 1. The new completion time of the project start_N must be equal to the previous completion time minus the advance save_N, which leads to the following constraint:

start_N = bestend - save_N

The objective defined by the second question is to maximize the builder's profit. For every week finished early, he receives a bonus of BONUS k. In exchange, the savings in time for a task i costs COST_i k (column `Add. cost per week' of Table Data for stadium construction). We thus obtain the following objective function.

maximize BONUS · save_N -

∑

_{i ∈ TASKS \ {N}}

COST_i · save_i

The complete mathematical model consists of the constraints and the objective function explained above, and the non-negativity conditions for variables start_i and save_i:

maximize BONUS · save_N -

∑

_{i ∈ TASKS \ {N}}

COST_i · save_i
∀ (i,j) ∈ ARCS: start_i + DUR_i - save_i ≤ start_j
start_N = bestend - save_N
∀ i ∈ TASKS \ {N}: save_i ≤ MAXW_i
∀ i ∈ TASKS: start_i ≥ 0, save_i ≥ 0

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 main model.

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 calling (main) 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 main 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) main 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

Results for question 2

The model above produces the following output. Setting XPRS_VERBOSE to true makes the software display the log of the LP solver: some information about the problem size (numbers of constraints, variables, non-zero coefficients, and MIP entities) and a log of the simplex algorithm. If you re-run the model without the bound updates from CP to LP you may observe a slightly larger number of Simplex iterations.

CP solution (version 1):
Earliest possible completion time: 64 weeks
1: 0, 2: 2, 3: 18, 4: 18-29, 5: 27, 6: 37
7: 26-61, 8: 43-59, 9: 43, 10: 26-59, 11: 43-58, 12: 52
13: 28-63, 14: 18-53, 15: 26-60, 16: 46-61, 17: 54, 18: 63
CP solution (version 2):
Earliest possible completion time: 52 weeks
1: 0-12, 2: 2-14, 3: 15-27, 4: 15-37, 5: 23-35, 6: 31-43
7: 21-62, 8: 36-60, 9: 36-48, 10: 21-60, 11: 36-60, 12: 43-55
13: 22-63, 14: 15-57, 15: 21-62, 16: 38-62, 17: 45-57, 18: 51-63

Reading Problem /xprs_6cf5_404d0008
Problem Statistics
          28 (      0 spare) rows
          38 (      0 spare) structural columns
          83 (      0 spare) non-zero elements
Global Statistics
           0 entities        0 sets        0 set members

   Its         Obj Value      S   Ninf  Nneg        Sum Inf  Time
     0        360.000300      D     17     0      29.000010     0
    17         87.000000      D      0     0        .000000     0
Optimal solution found
Total profit: 87
Total duration: 54 weeks
 1: 0   2: 2   3: 15  4: 15  5: 23  6: 31
 7: 23  8: 36  9: 36 10: 23 11: 36 12: 45
13: 25 14: 15 15: 23 16: 39 17: 47 18: 53

© 2001-2025 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.

Contents

Index

Glossary

Search Results