Constraint handling

In this section we shall work once more with the introductory problem of scheduling meetings from Section A first model. This model only contains simple arithmetic constraints over discrete variables. However, all that is said here equally applies to all other constraint types of Xpress Kalis, including constraint relations over continuous decision variables (that is, variables of the type cpfloatvar).

We now wish to state a few more constraints for this problem.

1. Meeting B must take place before day 3.
2. Meeting D cannot take place on day 2.
3. Meeting A must be scheduled on day 1.

Model formulation

The three additional constraints translate into simple (unary) linear constraints. We complete our model as follows:

Implementation

The Mosel implementation of the new constraints is quite straightforward.

model "Meeting (2)"
 uses "kalis"

 declarations
  MEETINGS = {'A','B','C','D'}        ! Set of meetings
  TIME = 1..3                         ! Set of time slots
  plan: array(MEETINGS) of cpvar      ! Time slot per meeting
 end-declarations

 forall(m in MEETINGS) do
  setdomain(plan(m), TIME)
  setname(plan(m), "plan"+m)
 end-do
 writeln("Original domains: ", plan)

 plan('B') <= 2                       ! Meeting B before day 3
 plan('D') <> 2                       ! Meeting D not on day 2
 plan('A') = 1                        ! Meeting A on day 1
 writeln("With constraints: ", plan)

! Respect incompatibilities
 plan('A') <> plan('B')
 plan('A') <> plan('D')
 plan('B') <> plan('C')
 plan('B') <> plan('D')

! Solve the problem
 if not(cp_find_next_sol) then
  writeln("Problem is infeasible")
  exit(1)
 end-if

! Solution printing
 forall(m in MEETINGS)
  writeln("Meeting ", m, ": ", getsol(plan(m)))

end-model

Results

As the reader may have noticed, we have added printout of the variables plan_m at several places in the model. The output generated by the execution of this model therefore is the following.

Original domains: [planA[1..3],planB[1..3],planC[1..3],planD[1..3]]
With constraints: [planA[1],planB[1..2],planC[1..3],planD[1,3]]
Meeting A: 1
Meeting B: 2
Meeting C: 1
Meeting D: 3 

As can be seen from this output, immediately after stating the constraints, the domains of the concerned variables have been reduced. The constraints are immediately and automatically posted to the solver and their effects are propagated to the whole problem.

Naming constraints

Sometimes it may be necessary to access constraints later on, after their definition, in particular if they are to become part of logic relations or if they are to be branched on (typically the case for disjunctive constraints). To this aim Xpress Kalis defines a new type, cpctr, that can be used to declare constraints giving them a name that can used after their definition. We define constraints by assigning to them a constraint relation.

Naming constraints has the secondary effect that the constraints are not automatically posted to the solver. This needs to be done by writing the name of a constraint as a statement on its own (after its definition) as shown in the following model.

model "Meeting (3)"
 uses "kalis"

 declarations
  MEETINGS = {'A','B','C','D'}        ! Set of meetings
  TIME = 1..3                         ! Set of time slots
  plan: array(MEETINGS) of cpvar      ! Time slot per meeting
  Ctr: array(range) of cpctr
 end-declarations

 forall(m in MEETINGS) do
  setdomain(plan(m), TIME)
  setname(plan(m), "plan"+m)
 end-do
 writeln("Original domains: ", plan)

 Ctr(1):= plan('B') <= 2              ! Meeting B before day 3
 Ctr(2):= plan('D') <> 2              ! Meeting D not on day 2
 Ctr(3):= plan('A') = 1               ! Meeting A on day 1
 writeln("After definition of constraints:\n ", plan)

 forall(i in 1..3) Ctr(i)
 writeln("After posting of constraints:\n ", plan)

! Respect incompatibilities
 plan('A') <> plan('B')
 plan('A') <> plan('D')
 plan('B') <> plan('C')
 plan('B') <> plan('D')

! Solve the problem
 if not(cp_find_next_sol) then
  writeln("Problem is infeasible")
  exit(1)
 end-if

! Solution printing
 forall(m in MEETINGS) writeln("Meeting ", m, ": ", getsol(plan(m)))

end-model

From the output produced by this model, we can see that the mere definition of named constraints does not have any effect on the domains of the variables (the constraints are defined in Mosel but not yet sent to the Kalis solver). Only after stating the names of the constraints (that is, sending them to the solver) we obtain the same domain reductions as with the previous version of the model.

Original domains: [planA[1..3],planB[1..3],planC[1..3],planD[1..3]]
After definition of constraints:
 [planA[1..3],planB[1..3],planC[1..3],planD[1..3]]
After posting of constraints:
 [planA[1],planB[1..2],planC[1..3],planD[1,3]]
Meeting A: 1
Meeting B: 2
Meeting C: 1
Meeting D: 3 

Explicit posting of constraints

In all previous examples, we have silently assumed that posting the constraints does not lead to a failure (infeasibility detected by the solver). In practice, this may not always be a reasonable assumption. Xpress Kalis therefore defines the function cp_post that explicitly posts a constraint to the solver and returns the status of the constraint system after its addition (true for feasible and false for infeasible). This functionality may be of special interest for dealing with over-constrained problems to stop the addition of constraints once an infeasibility has been detected and to report back to the user which constraint has made the problem infeasible.

To use the explicit posting with cp_post, in the previous model we replace the line

 forall(i in 1..3) Ctr(i) 

with the following code.

 forall(i in 1..3)
  if not cp_post(Ctr(i)) then
   writeln("Constraint ", i, " makes problem infeasible")
   exit(1)
  end-if

The return value of the every constraint posting is checked and the program is stopped if the addition of a constraint leads to an infeasibility.

The output produced by this model version is exactly the same as what we have seen in the previous section.

Explicit constraint propagation

The behavior of constraints can also be influenced in a different way. If we turn automated constraint propagation off,

 setparam("KALIS_AUTO_PROPAGATE", false) 

then constraints posted to the solver are not propagated. In this case, constraint propagation will only be launched by a call to cp_propagate or by starting the enumeration (subroutines cp_find_next_sol, cp_minimize, etc.).