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.

Within Xpress Kalis, this type of backtrackable information is implemented by 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"

 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

!************ 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

!********************************************

 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

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 ]