Generation Mechanisms (Search) and Heuristics

After the constraints have been posted, one may want to try to find a solution satisfies all constraints.

The basic principle of generation (called “search”) is:

1. Find a free CSint variable var among allvars. Search is end if there is no free variable (all variables are already instantiated).

2. Reduce the domain of variable var. For example, select a value val in the domain of var and try to instantiate: cs_EQ(var, val).

   • If failed to reduce variable, then go to step 2 and try to reduce in another way. For example, select an another value val2 and instantiate selected variable.

   • If it successed, then go to step 1.

Basic Functions for Generation

IZBOOL cs_search(CSint **allvars, int nbVars, CSint *(*findFreeVar)(CSint **allvars, int nbVars))

This function tries to instantiate all the CSint variables referenced by allvars. It may fail if there is no solution.

The findFreeVar function finds a non-instantiated CSint variable among allvars.

IZBOOL cs_Vsearch(int nbVars, CSint *vint, ...)

cs_Vsearch() accepts a variable number of arguments (number specified by the first argument nbVars ).

Pre-defined Choice Functions

CSint *cs_findFreeVar(CSint **allvars, int nbVars)

The first non-instantiated CSint variable in allvars is returned.

CSint *cs_findFreeVarNbElements(CSint **allvars, int nbVars)

The non-instantiated CSint variable which has the lowest number of elements in its domain is returned.

CSint *cs_findFreeVarNbElementsMin(CSint **allvars, int nbVars)

Among the CSint variables which all have the same lowest number of elements, it returns the one with the lowest minimum domain.

CSint *cs_findFreeVarNbConstraints(CSint **allvars, int nbVars)

The non-instantiated CSint variable which is involved in the greatest number of constraints is returned.

For example, cs_findFreeVarNbElements() could be defined as:

CSint *cs_findFreeVarNbElements(CSint **allvars, int nbVars) {
  int i;
  int nbElements, nbElementsOpt;
  CSint *varOpt = NULL;

  nbElementsOpt = INT_MAX;
  for (i = 0; i < nbVars; i++) {
    nbElements = cs_getNbElements(allvars[i]);
    if ((nbElements > 1) && (nbElements < nbElementsOpt)) {
      nbElementsOpt = nbElements;
      varOpt = allvars[i];
    }
  }
  return(varOpt);
}

Number of Fails and Choice Points

One can define heuristics that may depend on the number of Fails or the number of Choice Points that have occured, using these functions:

int cs_getNbFails()

Returns the number of Fails that have occured until this call. Functions that manage this parameter are:

• cs_search()

• cs_searchFail()

• cs_Vsearch()

• cs_searchCriteria()

• cs_searchCriteriaFail()

• cs_searchValueSelectorFail()

• cs_searchValueSelectorRestartNG()

• cs_searchMatrix()

• cs_searchMatrixFail()

• cs_findAll()

• cs_minimize()

int cs_getNbChoicePoints()

Returns the number of Choice Points that have been raised until this call. Functions that manage this parameter are same as cs_getNbFails().

Sophisticated Generation Functions

IZBOOL cs_searchCriteria(CSint **allvars, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int (*criteria)(int index, int val))

In cs_search(), when a CSint variable var has been chosen, the values are tried in increasing order (from cs_getMin(var) to cs_getMax(var), avoiding all the values which are not in the domain of var ).

cs_searchCriteria() enables to control this selection order. The value which minimize criteria() will be selected first.

IZBOOL cs_searchMatrix(CSint ***matrix, int NbRows, int NbCols, int (*findFreeRow)(CSint ***matrix, int NbRows, int NbCols), int (*findFreeCol)(int row, CSint **Row, int NbCols), int (*criteria)(int row, int col, int val))

cs_search() and cs_searchCriteria() are used to generate a vector of CSint variables.

cs_searchMatrix() does the same for a matrix. findFreeRow() returns the index of the Row the user wants to chose. After a row has been chosen, findFreeCol() returns the index of the Col to be chosen. After a CSint variable (Col, Row) has been chosen, a value which minimize criteria() is selected.

IZBOOL cs_searchFail(CSint **allvars, int nbVars, CSint *(*findFreeVar)(CSint **allvars, int nbVars), int NbFailsMax)

cs_searchFail() is similar to cs_search() except that it stops, and return FALSE (i.e. fails) if the number of backtracks reaches NbFailsMax.

One can check if the fail has occured because of the number of backtracks by checking NbFails (cf. cs_getNbFails() function).

IZBOOL cs_searchCriteriaFail(CSint **allvars, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int (*criteria)(int index, int val), int NbFailsMax)

cs_searchCriteriaFail() is similar to cs_searchCriteria() except that it stops, and return FALSE (i.e. fails) if the number of backtracks reaches NbFailsMax.

One can check if the fail has occured because of the number of backtracks by checking NbFails (cf. cs_getNbFails() function).

IZBOOL cs_searchValueSelectorFail(CSint **allvars, const CSvalueSelector **selectors, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int NbFailsMax, const CSsearchNotify *notify)

cs_searchValueSelectorFaill() tries to reduce domain of CSint variable using method specified by selectors. selectors is a array of pointer to CSvalueSelector variable which was created by cs_getValueSelector() or cs_createValueSelector(). This array must has nbVars elements.

NbFailsMax is treated as maximum fails like cs_searchFail().

notify is a CSsearchNotify type variable to set notification functions. (see cs_createSearchNotify()) notify can be NULL If functionality is not needed.

IZBOOL cs_searchValueSelectorRestartNG(CSint **allvars, const CSvalueSelector **selectors, int nbVars, int (*findFreeVar)(CSint **allvars, int nbVars), int (*maxFailFunction)(void *state), void *maxFailState, int nbFailsMax, CSnoGoodSet *ngs, const CSsearchNotify *notify)

cs_searchValueSelectorRestartNG() is similar to cs_searchValueSelectorFail() but restart and NoGood is added.

At first, search is executed using returned value of maxFailFunction as a maximum fail count. If solution is not found, maxFailFunction is called again to get new maximum fail count and search is executed again.

maxFailState is passed to maxFailFunction as a parameter.

Failed variable-value combination (NoGood) is recored in ngs which is created by cs_createNoGoodSet() to avoid same failure. (By limitatin of space and time, not all NoGoods are recorded.)

notify is a CSsearchNotify type variable to set notification functions. (see cs_createSearchNotify())

ngs and *notify can be NULL If functionality is not needed.

Typically, cs_searchValueSelectorRestartNG() is called like following:

static int findFreeVarIndex(CSint **allvars, int nbVars) {
    for (int i = 0; i < nbVars; i++) {
        if (cs_isFree(allvars[i]))
            return i;
    }

    return -1;
}

static int nextFail(void* state) {
    int* pn = (int*)state;
    int ret = *pn;

    *pn = ret + 10;

    return ret;
}

/* ... */
    const CSvalueSelector** vs = malloc(sizeof(CSvalueSelector*) * nbVars);
    CSnoGoodSet* ngs = cs_createNoGoodSet(allvars, nbVars, NULL, 0, NULL, NULL);
    CSsearchNotify* notify = cs_createSearchNotify(NULL);

    int fail = 10;

    for (int i = 0; i < nbVars; i++) {
        vs[i] = cs_getValueSelector(CS_VALUE_SELECTOR_MIN_TO_MAX);
    }

    cs_searchValueSelectorRestartNG(allvars, vs, nbVars, findFreeVarIndex, nextFail, &fail, 100000, ngs, notify);
/* ... */

IZBOOL cs_searchMatrixFail(CSint ***matrix, int NbRows, int NbCols, int (*findFreeRow)(CSint ***matrix, int NbRows, int NbCols), int (*findFreeCol)(int row, CSint **Row, int NbCols), int (*criteria)(int row, int col, int val), int NbFailsMax)

cs_searchMatrixFail() is similar to cs_searchMatrix() except that it stops, and return FALSE (i.e. fails) if the number of backtracks reaches NbFailsMax.

One can check if the fail has occured because of the number of backtracks by checking NbFails (cf. cs_getNbFails() function).

IZBOOL cs_findAll(CSint **allvars, int nbVars, CSint *(*findFreeVar)(CSint **allvars, int nbVars), void (*found)(CSint **allvars, int nbVars))

Search for all possible solutions. Each time a solution is found, the found() function is called.

Typically, the found() function can be used to display the solutions:

void found(CSint **allvars, int nbVars) {
  static NbSolutions = 0;
  printf("Solution %d\n", ++NbSolutions);
  cs_printf("%A\n\n", allvars, nbVars);
}

IZBOOL cs_minimize(CSint **allvars, int nbVars, CSint *(*findFreeVar)(CSint **allvars, int nbVars), CSint *cost, void (*found)(CSint **allvars, int nbVars, CSint *cost))

Try to find a solution minimizing the cost. At each step of the minimization, the found() function is called.

Typically, the found function can be used to display the current solution:

void found(CSint **allvars, int nbVars, CSint *cost) {

  static NbSolutions = 0;

  printf("Solution %d\n", ++NbSolutions);
  cs_printf("%A\n", allvars, nbVars);
  cs_printf("Cost = %T\n\n", cost);
}

cs_minimize() could be defined as:

IZBOOL cs_minimize(CSint **allvars, int nbVars, CSint* (*findFreeVar)(CSint **allvars, int nbVars),  CSint *cost, void (*found)(CSint **allvars, int nbVars, CSint *cost)) {
  char gFirst, g;
  gFirst = g = cs_search(allvars, nbVars, findFreeVar);
  while (g) {
    int currentCost = getMin(cost);
    found(allvars, nbVars, cost);
    cs_restoreAll();
    g = (cs_LT(cost, currentCost) && cs_search(allvars, nbVars, findFreeVar));
  }
  return gFirst;
}

To Stop Search Functions

void cs_cancelSearch(void)

Stop search at safe place. This function may be called from different thread from the thread search is running. Context may need to be restored using cs_restoreContextUntil().

Domain Reduction

Following search functions takes CSvalueSelector type variables as paramter and can reduce a domain using various methods.

• cs_searchValueSelectorFail()

• cs_searchValueSelectorRestartNG()

Pre-defined Methods for Domain Reduction

const CSvalueSelector *cs_getValueSelector(int vs)

Get pre-defined CSvalueSelector instance. Following values can be specified as vs .

CS_VALUE_SELECTOR_MIN_TO_MAX

Try single values in domain from minimum to maximum.

CS_VALUE_SELECTOR_MAX_TO_MIN

Try single values in domain from maximum to minimum.

CS_VALUE_SELECTOR_LOWER_AND_UPPER

Split domain using average of minimum and maximum value. Try lower half (including split value) and try rest of domain.

CS_VALUE_SELECTOR_UPPER_AND_LOWER

Split domain using average of minimum and maximum value. Try upper half (including split value) and try rest of domain.

CS_VALUE_SELECTOR_MEDIAN_AND_REST

Try median value of domain and try to remove that value.

User Defined Domain Reduction

Method for domain reduction can be defined by user. To define method for domain reduction, create CSvalueSelector type variable via cs_createValueSelector() and return CSvalueSelection type variable to generation function.

CSvalueSelector *cs_createValueSelector(IZBOOL (*init)(int index, CSint **vars, int size, void *pData), IZBOOL (*next)(CSvalueSelection *r, int index, CSint **vars, int size, void *pData), IZBOOL (*end)(int index, CSint **vars, int size, void *pData))

Define method for domain reduction as CSvalueSelector type variale. init, next, end are pointer to functions used to initialize(i.e constructor), enumerate, finalize(i.e destructor) respectively.

• init (function called once before domain reduction of a variable)

  • index : Index of varibale in vars

  • vars : Array of CSint variables

  • size : Size of vars

  • pData : Pointer to arbitrary data can store pointer or int

  • return value: TRUE if success

• next (function to enumerate domain reduction of a variable)

  • r : Pointer to CSvalueSelection type variable to set domain reduction.

  • index : Index of varibale in vars

  • vars : Array of CSint variables

  • size : Size of vars

  • pData : Pointer to arbitrary data can store pointer or int

  • return value: TRUE if valid r is set.

• end (function called once after all domain reductions of a variable are done)

  • index : Index of varibale in vars

  • vars : Array of CSint variables

  • size : Size of vars

  • pData : Pointer to arbitrary data can store pointer or int. If malloc-ed memory is pointed by this variable, it must be free-ed in end function.

  • return value: TRUE if success

Returned CSvalueSelector type variable must be released by calling cs_freeValueSelector() after used.

void cs_freeValueSelector(CSvalueSelector *vs)

Release CSvalueSelector type variable created by cs_createValueSelector().

Functions and Types Related to Domain Reduction

type CSvalueSelection

CSvalueSelection type describes how to reduce a domain of variable. It is defined as:

typedef struct {
  int method;
  int value;
} CSvalueSelection;

method means how to reduce a domain using value stored in value.

method field is used as described below:

CS_VALUE_SELECTION_EQ

Select a value form a domain.

CS_VALUE_SELECTION_NEQ

Remove a value form a domain.

CS_VALUE_SELECTION_LE

Select range less than or equal to value

CS_VALUE_SELECTION_LT

Select range less than value

CS_VALUE_SELECTION_GE

Select range greater than or equal to value

CS_VALUE_SELECTION_GT

Select range greater than value

IZBOOL cs_initValueSelector(const CSvalueSelector *vs, int index, CSint **vars, int size, void *pData)

Prepare to reduce a domain of CSint variable at index in array vars having size elements. pData is pointer to arbitrary data can store pointer or int.

Returns TRUE if successed.

IZBOOL cs_selectNextValue(CSvalueSelection *r, const CSvalueSelector *vs, int index, CSint **vars, int size, void *pData)

Try to get domain reduction into vs for CSint variable at index in array vars having size elements. pData is pointer to arbitrary data can store pointer or int.

Returns TRUE if successed to store domain reduction into vs. Returns FALSE when all domain reductions is already enumerated.

IZBOOL cs_endValueSelector(const CSvalueSelector *vs, int index, CSint **vars, void *pData)

Finilize a process of domain reduction for variable at index in array vars having size elements. pData is pointer to arbitrary data can store pointer or int.

Returns TRUE if successed.

IZBOOL cs_selectValue(CSint *v, const CSvalueSelection *vs)

Apply domain reduction stored in vs to CSint variable v.

Returns TRUE if successed.

Management of NoGood

cs_searchValueSelectorRestartNG() records failed variable-value combination into CSnoGoodSet variable as NoGood.

CSnoGoodSet *cs_createNoGoodSet(CSint **vars, int size, IZBOOL (*prefilter)(CSnoGoodSet *ngs, CSnoGood *ng, CSint **vars, int size, void *ext), int maxNoGood, void (*destructorNotify)(CSnoGoodSet *ngs, void *ext), void *ext)

Create a area to record NoGoods.

• vars : Array of CSint variable for search function.

• size : Sizeof array vars

• prefilter : Function to decide whether record NoGood into this CSnoGoodSet variable.

• maxNoGood : Maximum count of NoGoods recorded in this CSnoGoodSet variable.

• destructorNotify : Created CSnoGoodSet variable is released automatically when context is restored. destructorNotify is called when this variable is released. Specify NULL if this functionality is not needed.

• ext :Passed to prefilter and destructorNotify.

prefilter is called with:

• ngs : Variable created with this call of cs_createNoGoodSet()

• ng : Pointer to NoGood.

• vars, size and ext : Same as this call of cs_createNoGoodSet()

destructorNotify is called with:

• ngs : Variable created with this call of cs_createNoGoodSet()

• vars, size and ext : Same as this call of cs_createNoGoodSet()

int cs_getNbNoGoods(CSnoGoodSet *ngs)

Returns count of NoGoods in ngs.

int cs_getNbNoGoodElements(CSnoGood *ng)

Returns count of elements in NoGood ng. Elements can be retrieved using c:func:cs_getNoGoodElementAt.

void cs_getNoGoodElementAt(int *pIndex, CSvalueSelection *vs, CSnoGood *ng, int index)

Get information of element at index in ng.

• pIndex: Position in the array vars passed to cs_createNoGoodSet()

• vs: Failed domain reduction

void cs_filterNoGood(CSnoGoodSet *ngs, IZBOOL (*filter)(CSnoGoodSet *ngs, CSnoGood *elem, CSint **vars, int size, void *ext), void *ext)

Scan NoGoods registered in ngs and remove NoGoods which filter returns FALSE. Parameteres for filter is same as prefilter of cs_createNoGoodSet().

void cs_addNoGood(CSnoGoodSet *ngs, int *index, CSvalueSelection *vs, int size)

Add a NoGood to ngs. index is an array of index of variable and vs is an array of CSvalueSelection. size is size of these arrays.

void cs_setMaxNbNoGoods(CSnoGoodSet *ngs, int max)

Set max count of NoGoods stored in ngs.

Notifications of Search state

Search functions which take CSsearchNotify type parameter can notify their state using callback functions.

CSsearchNotify *cs_createSearchNotify(void *ext)

Create SsearchNotify type variable to pass to search function. ext will be passed to callback functions.

Created variable must be released using cs_freeSearchNotify().

void cs_freeSearchNotify(CSsearchNotify *notify)

Release a varibale created using cs_createSearchNotify().

void cs_searchNotifySetSearchStart(CSsearchNotify *notify, void (*searchStart)(int maxFails, CSint **allvars, int nbVars, void *ext))

Register a function searchStart called when start of search.

In cs_searchValueSelectorRestartNG(), searchStart will be called at every restart.

Following parameters are passed to searchStart.

• maxFails : Maximum fails allowed to starting search

• allvars : Array of CSint for search function

• nbVars : Size of allvars

• ext : Pointer passed to cs_createSearchNotify()

void cs_searchNotifySetSearchEnd(CSsearchNotify *notify, void (*searchEnd)(IZBOOL result, int nbFails, int maxFails, CSint **allvars, int nbVars, void *ext))

Register a function searchEnd called when search is done..

In cs_searchValueSelectorRestartNG(), searchEnd will be called at every end of restart.

Following parameters are passed to searchEnd.

• result : TRUE when solution is found. Otherwise FALSE

• nbFails : Count of fails occured while this search

• maxFails : Maximum fails allowed to this search

• allvars : Array of CSint for search function

• nbVars : Size of allvars

• ext : Pointer passed to cs_createSearchNotify()

void cs_searchNotifySetBeforeValueSelection(CSsearchNotify *notify, void (*beforeValueSelection)(int depth, int index, const CSvalueSelection *vs, CSint **allvars, int nbVars, void *ext))

Register a function beforeValueSelection called before domain reduction is applied to CSint variable.

Following parameteres are passed to beforeValueSelection.

• depth : Depth of search

• index : Index of variable in allvars

• vs : Method of domain reduction.

• allvars : Array of CSint for search function

• nbVars : Size of allvars

• ext : Pointer passed to cs_createSearchNotify()

void cs_searchNotifySetAfterValueSelection(CSsearchNotify *notify, void (*afterValueSelection)(IZBOOL result, int depth, int index, const CSvalueSelection *vs, CSint **allvars, int nbVars, void *ext))

Register a function afterValueSelection called after domain reduction is applied to CSint variable. Following parameters are passed to afterValueSelection.

• result : TRUE if domain reductions is done successfully. Otherwise FALSE

• depth : Depth of search

• index : Index of variable in allvars

• vs : Method of domain reduction.

• allvars : Array of CSint for search function

• nbVars : Size of allvars

• ext : Pointer passed to cs_createSearchNotify()

void cs_searchNotifySetEnter(CSsearchNotify *notify, void (*enter)(int depth, int index, CSint **allvars, int nbVars, void *ext))

Register a function enter called when CSint variable is selected to reduce its domain.

Following parameters are passed to enter.

• depth : Depth of search

• index : Index of selected variable in allvars

• allvars : Array of CSint for search function

• nbVars : Size of allvars

• ext : Pointer passed to cs_createSearchNotify()

void cs_searchNotifySetLeave(CSsearchNotify *notify, void (*leave)(int depth, int index, CSint **allvars, int nbVars, void *ext))

Register a function leave called after all reduction methods are tried to CSint variable.

Following parameters are passed to leave.

• depth : Depth of search

• index : Index of selected variable in allvars

• allvars : Array of CSint for search function

• nbVars : Size of allvars

• ext : Pointer passed to cs_createSearchNotify()

void cs_searchNotifySetFound(CSsearchNotify *notify, IZBOOL (*found)(int depth, CSint **allvars, int nbVars, void *ext))

Register a function found called when a solution is found.

Following parameters are passed to found.

• depth : Depth of search

• allvars : Array of CSint for search function

• nbVars : Size of allvars

• ext : Pointer passed to cs_createSearchNotify()

If found returns TRUE, search function ends with return value TRUE. Otherwise search will be continued.

This callback is called multiple time on same solution when search function uses restart.