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.

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.

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:

Parallel machine assignment

The objective function to be maximized sums the output_p variables.

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.

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
   HProd: integer                    ! Total productivity value
   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.

 procedure print_sol(text1,text2:string, objval:integer)
  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.

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

 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):

 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.

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.