Enumeration

Topics covered in this chapter:

This chapter gives an overview on different issues related to the definition of search strategies with Xpress Kalis in Mosel, namely

• predefined search strategies,
• means of interrupting and restarting the enumeration,
• search callbacks, and
• the definition of user search strategies.

The last section discusses what may be done in the case of an infeasible constraint system:

• analyzing infeasibility and handling conflicts

Predefined search strategies

With Xpress Kalis a branching strategy is composed of three components:

• The branching scheme determines the shape of the search tree, this includes exhaustive schemes like assign_var and split_domain (enumeration of decision variables), settle_disjunction (enumeration over constraints), and task_serialize (enumeration of tasks in scheduling problems), or potentially incomplete searches with probe_assign_var or probe_settle_disjunction.
• The variable selection strategy determines the choice of the branching variables. Predefined selection criteria include

  KALIS_INPUT_ORDER

  variables in the given order,

  KALIS_LARGEST_MAX

  variable with largest upper bound,

  KALIS_LARGEST_MIN

  variable with largest lower bound,

  KALIS_MAX_DEGREE

  variable occurring in the largest number of constraints,

  KALIS_MAXREGRET_LB

  variable with largest difference between its lower bound and second-smallest domain value,

  KALIS_MAXREGRET_UB

  variable with largest difference between its upper bound and second-largest domain value,

  KALIS_RANDOM_VARIABLE

  random variable choice,

  KALIS_SDOMDEG_RATIO

  variable with smallest ratio domain size / degree,

  KALIS_SMALLEST_DOMAIN

  variable with smallest number of domain values/smallest domainintervall,

  KALIS_SMALLEST_MAX

  variable with smallest upper bound,

  KALIS_SMALLEST_MIN

  variable with smallest lower bound).

  KALIS_WIDEST_DOMAIN

  variable with largest number of domain values/largest domain interval,

  The user may also define his own variable selection strategy (see Section User search below).
• The value selection strategy determines the choice of the branching value once the variable to be branched on is known. The following predefined selection criteria are available.
  

  KALIS_MAX_TO_MIN

  enumeration of values in decreasing order,

  KALIS_MIDDLE_VALUE

  enumerate first values in the middle of the variable's domain,

  KALIS_MIN_TO_MAX

  enumeration of values in increasing order,

  KALIS_NEAREST_VALUE

  choose the value closest to a target value previously specified with settarget,

  KALIS_RANDOM_VALUE

  choose a random value out of the variable's domain.

  The predefined criteria can be replaced by the user's own value selection strategy (see Section User search below).

Depending on the choice of the branching scheme, it may be possible to specify additional parameters to configure the enumeration. The reader is referred to the Xpress Kalis Mosel Reference Manual for further detail. In the case of constraint branching, there is quite obviously no variable or branching value selection. The special case of task-based branching strategies (branching scheme task_serialize) is discussed in Section Enumeration. Enumeration of continuous variables (type cpfloatvar) always uses the branching scheme split_domain with the KALIS_SMALLEST_DOMAIN or KALIS_WIDEST_DOMAIN variable selection (the former is used by the default strategy, the latter often works better in purely continuous problems) and only a subset of the value selection strategies listed above.

Branching strategies may be defined for certain specified variables (or, where applicable, constraints or tasks), or, if the corresponding argument of the branching scheme function is left out, are applied to all decision variables in a model (see, for instance, model b4seq_ka.mos in Section element: Sequencing jobs on a single machine).

If the user's model does not specify any branching strategy, then the Kalis solver will apply default strategies to enumerate all variables in the model. Even if one does not wish to change the default enumeration (for discrete variables: `smallest domain first' and `smallest value first'), it may still be desirable to define a branching strategy to fix a certain order for the enumeration of different groups of decision variables. The previous chapter contains several examples of this: in the model a4sugar_ka.mos (Section occurrence: Sugar production) we define an enumeration over some of the variables of a model, giving them thus preference over the remainder. In model j5tax_ka.mos (Section equiv: Location of income tax offices) we have seen an example of a search strategy composed of different enumerations for groups of decision variables.

If a model contains both, discrete and continuous variables (cpvar and cpfloatvar) the default strategies enumerate first the discrete and then the continuous variables.

Interrupting and restarting the search

When solving large applications it is often not possible to enumerate the complete search tree within a reasonable time span. Several stopping criteria are therefore available in Xpress Kalis to interrupt the search. These are

KALIS_MAX_BACKTRACKS

maximum number of backtracks,

KALIS_MAX_COMPUTATION_TIME

limit on total time spent in search,

KALIS_MAX_DEPTH

maximum search tree depth,

KALIS_MAX_NODES

maximum number of nodes to explore,

KALIS_MAX_SOLUTIONS

maximum number of solutions,

KALIS_OPT_ABS_TOLERANCE

absolute difference between the objective function value in a solution and its best possible value (= current upper bound on objective function in maximization problems and lower bound with minimization),

KALIS_OPT_REL_TOLERANCE

relative difference between the objective function value in a solution and its best possible value (= current upper bound on objective function in maximization problems and lower bound with minimization).

These parameters are accessed with the Mosel functions setparam and getparam (see, for example, the output of problem statistics in model sudoku_ka.mos in Section all_different: Sudoku, and the search time limit set in the model freqasgn.mos of Section abs and distance: Frequency assignment).

In optimization problems, after a solution has been found the search continues from this point unless the setting of parameter KALIS_OPTIMIZE_WITH_RESTART is changed. The same is true if the search is interrupted by means of one of the above-named criteria and then continued, for instance with a different search strategy. To restart the search from the root node the procedure cp_reset_search needs to be called (as an example, see model freqasgn.mos in Section abs and distance: Frequency assignment)

Callbacks

During the search the user's model may interact with the solver at certain predefined points by means of callback functions. This functionality is particularly useful to retrieve solution information for intermediate solutions during an optimization run as shown in the model freqasgn.mos (Section abs and distance: Frequency assignment). Other than this solution callback, the user may set functions that will be called at every branch or at every node (see the Xpress Kalis Mosel Reference Manual for further detail).

User-defined enumeration strategies

The following problem description is taken from Section 14.1 of `Applications of optimization with Xpress-MP'.

An operator needs to be assigned to each of the six machines in a workshop. Six workers have been pre-selected. Everyone has undergone a test of her productivity on every machine. Table Productivity in pieces per hour lists the productivities in pieces per hour. The machines run in parallel, that is, the total productivity of the workshop is the sum of the productivities of the people assigned to the machines.

Table 4.1: Productivity in pieces per hour

	Machines
Workers	1	2	3	4	5	6
1	13	24	31	19	40	29
2	18	25	30	15	43	22
3	20	20	27	25	34	33
4	23	26	28	18	37	30
5	28	33	34	17	38	20
6	19	36	25	27	45	24

The objective is to determine an assignment of workers to machines that maximizes the total productivity. We may start by calculating a (non-optimal) heuristic solution using the following fairly natural method: choose the assignment p → m with the highest productivity, cross out the line p and the column m (since the person has been placed and the machine has an operator), and restart this process until we have assigned all persons—the resulting assignment is highlighted in bold print in the data table. However, our aim really is to solve this problem to optimality for the case of parallel machines and also for machines working in series.

Model formulation

This problem type is well known under the name of the assignment problem. Let PERS be the set of workers, MACH the set of machines (both of the same size N), and OUTP_pm the productivity of worker p on machine m. We define N integer variables assign_p taking values in the set of machines, where assign_p denotes the number of the machine to which the person p is assigned. The fact that a person p is assigned to a single machine m and a machine m is operated by a single person p is then expressed by the constraint that all variables assign_p take different values.

∀ p ∈ PERS: assign_p ∈ MACH
all-different(

⋃

m ∈ MACH

assign_p)

Furthermore, let output_p denote the output produced by person p. The values of these variables are obtained as discrete functions in the assign_p variables:

∀ p ∈ PERS: output_p = OUTP_p,assignp

Parallel machine assignment

The objective function to be maximized sums the output_p variables.

maximize

∑

p ∈ PERS

output_p

Certain assignments may be infeasible. In such a case, the value of the corresponding machine needs to be removed from the domain of the variable assign_p.

Machines working in series

If the machines work in series, the least productive worker on the machine she has been assigned to determines the total productivity of the workshop. An assignment will still be described by N variables assign_p and an all-different constraint on these variables. We also have the output_p variables with the constraints linking them to the values of the assign_p variables from the previous model. To this we add a variable pmin for the minimum productivity. The objective is to maximize pmin. This type of optimization problem where one wants to maximize a minimum is called maximin, or bottleneck.

maximize pmin
pmin = minimum_{p ∈ PERS}(output_p)

Implementation

The following Mosel program first implements and solves the model for the case of parallel machines. Afterwards, we define the variable pmin that is required for solving the problem for the case that the machines work in series.

model "I-1 Personnel assignment (CP)"
 uses "kalis"

 forward procedure parallel_heur
 forward procedure print_sol(text1,text2:string, objval:integer)

 declarations
  PERS = 1..6                        ! Personnel
  MACH = 1..6                        ! Machines
  OUTP: array(PERS,MACH) of integer  ! Productivity
 end-declarations

 initializations from 'Data/i1assign.dat'
  OUTP
 end-initializations

! **** Exact solution for parallel machines ****

 declarations
  assign: array(PERS) of cpvar       ! Machine assigned to a person
  output: array(PERS) of cpvar       ! Productivity of every person
  totalProd: cpvar                   ! Total productivity
  O: array(MACH) of integer          ! Auxiliary array for constraint def.
  Strategy: cpbranching              ! Branching strategy
 end-declarations

 forall(p in PERS) setdomain(assign(p), MACH)

! Calculate productivity per worker
 forall(p in PERS) do
  forall(m in MACH) O(m):= OUTP(p,m)
  element(O, assign(p)) = output(p)
 end-do

! Calculate total productivity
 totalProd = sum(p in PERS) output(p)

! One person per machine
 all_different(assign)

! Branching strategy
 Strategy:= assign_var(KALIS_LARGEST_MAX, KALIS_MAX_TO_MIN, output)
 cp_set_branching(Strategy)

! Solve the problem
 if cp_maximize(totalProd) then
  print_sol("Exact solution (parallel assignment)", "Total", getsol(totalProd))
 end-if

! **** Exact solution for serial machines ****

 declarations
  pmin: cpvar                        ! Minimum productivity
 end-declarations

! Calculate minimum productivity
 pmin = minimum(output)

! Branching strategy
 Strategy:= assign_var(KALIS_SMALLEST_MIN, KALIS_MAX_TO_MIN, output)
 cp_set_branching(Strategy)

! Solve the problem
 if cp_maximize(pmin) then
  print_sol("Exact solution (serial machines)", "Minimum", getsol(pmin))
 end-if

When the solution to the parallel assignment problem is found, we print out the solution and re-start the search with a new branching strategy and a new objective function. Since the first search has finished completely (no interruption by a time limit, etc.) there is no need to reset the solver between the two runs.

The branching strategy chosen for the parallel assignment problem is inspired by the intuitive procedure described in the introduction to Section User-defined enumeration strategies: instead of enumerating the possible assignments of workers to machines (= enumeration of the assign_p variables) we define an enumeration over the output_p variables, choosing the variable with the largest remaining value (KALIS_LARGEST_MAX) and branch on its values in decreasing order (KALIS_MAX_TO_MIN). For the second problem we need to proceed differently: to avoid being left with a small productivity value for some worker p we pick first the output_p variable with the smallest lower bound (KALIS_SMALLEST_MIN); again we enumerate the values starting with the largest one.

The following procedure parallel_heur may be added to the above program. It heuristically calculates a (non-optimal) solution to the parallel assignment problem using the intuitive procedure described in the introduction to Section User-defined enumeration strategies.

 procedure parallel_heur
  declarations
   ALLP, ALLM: set of integer        ! Copies of sets PERS and MACH
   pmax,omax,mmax: integer
  end-declarations

 ! Copy the sets of workers and machines
  forall(p in PERS) ALLP+={p}
  forall(m in MACH) ALLM+={m}

 ! Assign workers to machines as long as there are unassigned persons
  while (ALLP<>{}) do
   pmax:=0; mmax:=0; omax:=0

 ! Find the highest productivity among the remaining workers and machines
   forall(p in ALLP, m in ALLM)
    if OUTP(p,m) > omax then
     omax:=OUTP(p,m)
     pmax:=p; mmax:=m
    end-if

   assign(pmax) = mmax               ! Assign chosen machine to person pmax
   ALLP-={pmax}; ALLM-={mmax}        ! Remove person and machine from sets
  end-do

  writeln("Heuristic solution (parallel assignment):")
  forall(p in PERS)
   writeln("  ",p, " operates machine ", getval(assign(p)),
           " (",getval(output(p)), ")")
  writeln("  Total productivity: ", getval(totalProd))
 end-procedure

The model is completed with a procedure for printing out the solution in a properly formatted way.

  writeln(text1,":")
  forall(p in PERS)
   writeln("  ",p, " operates machine ", getsol(assign(p)),
           " (",getsol(output(p)), ")")
  writeln("  ", text2, " productivity: ", objval)
 end-procedure

end-model

User search

Instead of using predefined variable and value selection criteria as shown in all previous model implementations we may choose to define our own search heuristics. We now show how to implement the search strategies from the previous model `by hand.' In our implementation we add each time a second criterion for breaking ties in cases where the main criterion applies to several variables at a time.

Variable selection: the variable selection function has a fixed format—it receives as its argument a list of variables of type cpvarlist and it returns an integer, the list index of the chosen branching variable. The list of variables passed into the function may contain variables that are already instantiated. As a first step in our implementation we, therefore, determine the set Vset of yet uninstantiated variables—or to be more precise, the set of their indices in the list. The entries of the list of variables are accessed with the function getvar. Among the uninstantiated variables we calculate the set of variables Iset with the largest upper bound value (using function getub). Finally, among these variables, we choose the one with the smallest second-largest value (this corresponds to a maximum regret strategy). Predecessor (next-smallest) values in the domain of a decision variable are obtained with the function getprev. Inversely, we have function getnext for an enumeration of domain values in ascending order. The chosen index value is assigned to returned as the function's return value.

 public function varchoice(Vars: cpvarlist): integer
  declarations
   Vset,Iset: set of integer
  end-declarations

 ! Set of uninstantiated variables
  forall(i in 1..getsize(Vars))
   if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if

  if Vset={} then
   returned:= 0
  else
  ! Get the variable(s) with largest upper bound
   dmax:= max(i in Vset) getub(getvar(Vars,i))
   forall(i in Vset)
    if getub(getvar(Vars,i)) = dmax then Iset+= {i}; end-if
   dmin:= dmax

  ! Choose variable with smallest next-best value among those indexed by 'Iset'
   forall(i in Iset) do
    prev:= getprev(getvar(Vars,i),dmax)
    if prev < dmin then
     returned:= i
     dmin:= prev
    end-if
   end-do
  end-if
 end-function

The variable selection strategy varchoicemin for the second optimization run (serial machines) is implemented in a similar way. We first establish the set of variables with the smallest lower bound value (using getlb), Iset; among these we choose the variable with the smallest upper bound (getub).

 public function varchoicemin(Vars: cpvarlist): integer
  declarations
   Vset,Iset: set of integer
  end-declarations

 ! Set of uninstantiated variables
  forall(i in 1..getsize(Vars))
   if not is_fixed(getvar(Vars,i)) then Vset+= {i}; end-if

  if Vset={} then
   returned:= 0
  else
  ! Get the variable(s) with smallest lower bound
   dmin:= min(i in Vset) getlb(getvar(Vars,i))
   forall(i in Vset)
    if getlb(getvar(Vars,i)) = dmin then Iset+= {i}; end-if

  ! Choose variable with smallest upper bound among those indexed by 'Iset'
   dmax:= getparam("kalis_default_ub")
   forall(i in Iset)
    if getub(getvar(Vars,i)) < dmax then
     returned:= i
     dmax:= getub(getvar(Vars,i))
    end-if
  end-if
 end-function

Value selection: the value selection function receives as its argument the chosen branching variable and returns a branching value for this variable. The value selection criterion we have chosen (corresponding to KALIS_MAX_TO_MIN) is to enumerate all values for the branching variable, starting with the largest remaining one (that is, the variable's upper bound):

 public function valchoice(x: cpvar): integer
  returned:= getub(x)
 end-function

Notice that with an assign_var or assign_and_forbid strategy, the user's value selection strategy should make sure to return a value that is currently in the branching variable's domain (a value chosen between the lower and upper bound is not guaranteed to lie in the domain) by using function contains.

Setting user search strategies: to indicate that we wish to use our own variable or value selection strategy we simply need to replace the predefined constants by the name of our Mosel functions:

Strategy:= assign_var("varchoice", "valchoice", output)

defines the strategy for the first optimization run and

Strategy:= assign_var("varchoicemin", "valchoice", output)

re-defines it for the serial machine case. Since our function valchoice does just the same as the KALIS_MAX_TO_MIN criterion, we could also combine it with our variable choice function:

Strategy:= assign_var("varchoicemin", KALIS_MAX_TO_MIN, output)

Results

The following table summarizes the results found with the different solution methods for the two problems of parallel and serial machines. There is a notable difference between the heuristic method and the exact solution to the problem with parallel machines.

Table 4.2: Optimal assignments for different model versions

		Person
	Alg.	1	2	3	4	5	6	Productivity
Parallel Machines	Heur.	4 (19)	1 (18)	6 (33)	2 (26)	3 (34)	5 (45)	175
	Exact	3 (31)	5 (43)	4 (25)	6 (30)	1 (28)	2 (36)	193
Serial Machines	Exact	5 (40)	3 (30)	6 (33)	2 (26)	1 (28)	4 (27)	26

By adding output of solver statistics to our model (cp_show_stats) we find that our user search strategies result in the same search trees and program execution durations as with the predefined strategies for the parallel assignment and arrive at a slightly different solution for the serial case.

Reversible numbers

When developing your own search strategies and also in the implementation of user constraints it is sometimes helpful to be able to save some information related to a particular state of the constraint system and have the corresponding values restored automatically whenever the system returns to an earlier state during backtrack.

The kalis module implements this type of backtrackable information through the types cpreversible and cpreversiblearray. A reversible number is an object that takes integer or real values associated with a given state of the constraint system. Earlier values are restored when the system backtracks to the corresponding state.

The values of reversible numbers are stored with the constraint system, and as such one might be tempted to compare them with decision variables, but there is a fundamental difference between the two: the principle of incrementality does not apply to reversible numbers. Whereas the bounds on decision variables can only be reduced from any node to its descendants, the value of a reversible number might be any random sequence, such as 1 at the first node, -2 at its immediate child node, and 3 at the node of the next lower level. The following small example illustrates this. At every node, the coefficients of all fixed variables are saved in the array of reversibles ka and the reversible number k is the sum of the already fixed terms. The example further uses a reversible depth to save the current level in the branching tree. The 'branch-up' and 'branch-down' callbacks are used for displaying the current values of all numbers.

model "Tracing reversible numbers"
 uses "kalis", "mmsystem"

 forward procedure save_node_state
 forward procedure branch_up
 forward procedure branch_down

 declarations
   N = 5
   R = 1..N
   C: array(R) of integer

   x: array(R) of cpvar

   k,depth: cpreversible
   ka: cpreversiblearray
 end-declarations

 C::(1..5)[-7,15,-3,19,-45]

! Initialization: all reversible numbers at 0
 set_reversible_attributes(depth, 0)
 set_reversible_attributes(k, 0)
 set_reversible_attributes(ka, 1, N, 0)

! Decision variables and constraints
 forall(i in R) setdomain(x(i), 0, 1)
 sum(i in R) x(i) >= 3

 cp_set_node_callback(->save_node_state)
 cp_set_branch_callback(->branch_down, ->branch_up)

 cp_set_branching(assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MAX_TO_MIN))
 setparam("KALIS_MAX_SOLUTIONS", 3)
 while (cp_find_next_sol) do
  writeln(" "*2*round(depth.val), "Solution: ", x)
 end-do

!************ Callback functions ************
 procedure save_node_state
  setval(depth, getval(depth)+1)
  k.val:= sum(i in R) if(is_fixed(x(i)), C(i)*x(i).val, 0)
  forall(i in R) setelt(ka,i, if(is_fixed(x(i)), C(i)*x(i).val, 0))
 end-procedure

 procedure branch_up
  writeln(textfmt(" "*2*round(depth.val)+ "up  ",-20), k, "\t", ka)
 end-procedure

 procedure branch_down
  writeln(textfmt(" "*2*round(depth.val)+ "down  ",-20), k, "\t", ka)
 end-procedure

end-model

The output produced by the example is shown here, notice how the tree depth value is used to indent the lines, and observe how the values of reversibles change between nodes, in particular the value of the reversible number k.

    down            0.000000    [0 0 0 0 0 ]
      down          -7.000000   [-7 0 0 0 0 ]
        down        8.000000    [-7 15 0 0 0 ]
          down      5.000000    [-7 15 -3 0 0 ]
            down    24.000000   [-7 15 -3 19 0 ]
            Solution: [V001[1],V002[1],V003[1],V004[1],V005[1]]
          up        5.000000    [-7 15 -3 0 0 ]
            down    24.000000   [-7 15 -3 19 0 ]
            Solution: [V001[1],V002[1],V003[1],V004[1],V005[0]]
          up        5.000000    [-7 15 -3 0 0 ]
        up          8.000000    [-7 15 0 0 0 ]
          down      5.000000    [-7 15 -3 0 0 ]
            down    5.000000    [-7 15 -3 0 0 ]
            Solution: [V001[1],V002[1],V003[1],V004[0],V005[1]]
          up        5.000000    [-7 15 -3 0 0 ]
        up          8.000000    [-7 15 0 0 0 ]
      up            -7.000000   [-7 0 0 0 0 ]
    up              0.000000    [0 0 0 0 0 ]
  up                0.000000    [0 0 0 0 0 ]

Analyzing infeasibility and handling conflicts

In many cases the return status 'problem infeasible' or ' constraint inconsistent' is not a desirable situation since we really wish to find a solution to the problem we are solving. To support the user's analysis of the cause of the infeasibility Kalis can generate reports about sets of infeasible constraints. During the development of a model such a facility helps tracking model formulation errors and in applications inconsistencies in data are identified more easily.

We shall work once more with the Sudoku example from Section all_different: Sudoku. Instead of launching the enumeration through the CP solver we now prompt the user to input a value for a randomly chosen cell. If the value set by the user leads to an inconsistent state of the constraint system we invoke the solver display of the minimal set of constraints causing the infeasibility.

Implementation

The problem statement and setting of start data remain exactly the same as with the standard implementation of the problem seen in Section all_different: Sudoku. What is new are the prompt for user input and the subsequent handling of infeasibilities. The underlying mechanisms are markers (often referred to as choice points) to save the state of the constraint solver at a given moment and the possibility to return to the last such saved state. The corresponding Mosel subroutines are cp_save_state and cp_restore_state. After stating a new constraint but before propagating its effect (the automated propagation has been switched off through the setting of AUTO_PROPAGATE at the beginning of the model) we save the state of the constraint system. If the new constraint turns out to be infeasible the solver is set back to the state before the constraint propagation and we can then invoke the infeasibility analysis (cp_infeas_analysis).

The subroutine for solution printing has been replaced by a routine printing the values of all fixed variables.

model "Conflicts"
 uses "kalis"

 forward procedure print_values

 setparam("kalis_default_lb", 1)
 setparam("kalis_default_ub", 9)         ! Default variable bounds

 declarations
  XS = {'A','B','C','D','E','F','G','H','I'}   ! Columns
  YS = 1..9                              ! Rows
  v: array(XS,YS) of cpvar               ! Number assigned to cell (x,y)
 end-declarations

 forall(x in XS,y in YS) setname(v(x,y), "v("+x+","+y+")")

 setparam("KALIS_AUTO_PROPAGATE", 0)     ! Disable automatic propagation

! Data from "The Guardian", 29 July, 2005. http://www.guardian.co.uk/sudoku
 v('A',1)=8; v('F',1)=3
 v('B',2)=5; v('G',2)=4
 v('A',3)=2; v('E',3)=7; v('H',3)=6
 v('D',4)=1; v('I',4)=5
 v('C',5)=3; v('G',5)=9
 v('A',6)=6; v('F',6)=4
 v('B',7)=7; v('E',7)=2; v('I',7)=3
 v('C',8)=4; v('H',8)=1
 v('D',9)=9; v('I',9)=8


! All-different values in rows
 forall(y in YS) all_different(union(x in XS) {v(x,y)})

! All-different values in columns
 forall(x in XS) all_different(union(y in YS) {v(x,y)})

! All-different values in 3x3 squares
 forall(s in {{'A','B','C'},{'D','E','F'},{'G','H','I'}}, i in 0..2)
  all_different(union(x in s, y in {1+3*i,2+3*i,3+3*i}) {v(x,y)})

! Prompt user for new assignments
 declarations
  NX: array(1..9) of string
  val: integer
 end-declarations

 NX::(1..9)['A','B','C','D','E','F','G','H','I']
 cp_save_state
 res:=cp_propagate
 print_values
 setrandseed(3)

 while (res and (or(x in XS,y in YS) not is_fixed(v(x,y))) ) do
 ! Select randomly a yet unassigned cell
  rx:=round(0.5+9*random); ry:=round(0.5+9*random)
  while (is_fixed(v(NX(rx),ry))) do
   rx:=round(0.5+9*random); ry:=round(0.5+9*random)
  end-do

 ! Prompt for user input
  writeln(v(NX(rx),ry), " = ")
  readln(val)

 ! Add the new constraint
  v(NX(rx),ry)=val                     ! State a new constraint
  cp_save_state                        ! Save system state before propagation
  res:=cp_propagate                    ! Propagate the new constraint

 ! Print resulting board
  print_values
 end-do

! An infeasible state has been reached
 if not res then
  cp_restore_state                     ! Restore state before propagation
  cp_infeas_analysis                   ! Analyze infeasibility, print report
 else
  writeln("Problem solved")
 end-if

!****************************************************************
! Print fixed values
 procedure print_values
  writeln("   A B C   D E F   G H I")
  forall(y in YS) do
   write(y, ": ")
   forall(x in XS)
    write(if(is_fixed(v(x,y)), string(getval(v(x,y))), "."),
          if(x in {'C','F'}, " | ", " "))
   writeln
   if y mod 3 = 0 then
    writeln("   ---------------------")
   end-if
  end-do
 end-procedure

end-model

Results

With the following user value input sequence:

v(F,7)[1,5..6,8] =
1
v(I,1)[1..2,7,9] =
1
v(I,8)[2,6..7] =
2

we obtain an infeasibility for the third value. The values printed at this stage and the report generated by the solver show why this value leads to a conflict.

   A B C   D E F   G H I
1: 8 . . | . . 3 | . . 1
2: . 5 . | . . . | 4 . 7
3: 2 . 1 | . 7 . | . 6 9
   ---------------------
4: . . . | 1 . . | . . 5
5: . . 3 | . . . | 9 . .
6: 6 . . | . . 4 | . . 7
   ---------------------
7: . 7 . | . 2 1 | . . 3
8: . . 4 | . . . | . 1 2
9: . . . | 9 . . | . . 8
   ---------------------
------------------------
  Minimal Conflict Set
------------------------
  1 : AllDifferent(v(I,1),v(I,2),v(I,3),v(I,4),v(I,5),v(I,6),v(I,7),v(I,8),v(I,9
))

Note: in the present example we examine the effect of adding just a single (bound) constraint to our problem. However, the infeasibility analysis functionality can be applied for any number and type of constraints.