The CLP Procedure

PROC CLP Statement

  • PROC CLP options;

The PROC CLP statement invokes the CLP procedure. You can specify options to control a variety of search parameters that include selection strategies, assignment strategies, backtracking strategies, maximum running time, and number of solution attempts. You can specify the following options:

ACTDATA= SAS-data-set
ACTIVITY=SAS-data-set

identifies the input SAS data set that defines the activities and temporal constraints. The temporal constraints consist of time-alignment-type constraints and precedence-type constraints. The format of the ACTDATA= data set is similar to that of the Activity data set used by the CPM procedure in SAS/OR software. You can also specify the activities and time alignment constraints directly by using the ACTIVITY statement without the need for a data set. The CLP procedure enables you to define activities by using a combination of the two specifications.

CONDATA= SAS-data-set

identifies the input SAS data set that defines the constraints, variable types, and variable bounds. The CONDATA data set provides support for linear constraints only.

You can also specify the linear constraints in-line by using the LINCON statement. The CLP procedure enables you to define constraints by using a combination of the two specifications. When defining constraints, you must define the variables by using a VARIABLE statement or implicitly define them by specifying the USECONDATAVARS= option when using the CONDATA= data set. You can define variable bounds by using the VARIABLE statement, and any such definitions override those defined in the CONDATA= data set.

DECRMAXTIME

dynamically decreases the maximum solution time in effect during evaluation of the selection strategy. The DECRMAXTIME option is effective only when the EVALACTSEL= option or the EVALVARSEL= option is specified. Initially, the maximum solution time is the value specified by the MAXTIME= option. Whenever a solution is found with the current activity or variable selection strategy, the value of MAXTIME for future attempts is reduced to the current solution time. The DECRMAXTIME option thus provides a sense of which strategy is the fastest for a given problem. However, you must use caution when comparing the strategies in the macro variable , because the results pertain to different time limits.

By default, DECRMAXTIME is disabled; each activity or variable selection strategy is given the amount of time specified by the MAXTIME= option.

DM= m

specifies the dead-end multiplier for the scheduling CSP. The dead-end multiplier is used to determine the number of dead ends that are permitted before triggering a complete restart of the search technique in a scheduling environment. The number of dead ends is the product of the dead-end multiplier, m, and the number of unassigned activities. The default value is 0.15. This option is valid only with the SCHEDULE= option.

DOMAIN= [lb, ub]
DOM=[lb, ub]

specifies the global domain of all variables to be the closed interval [lb, ub]. You can override the global domain for a variable with a VARIABLE statement or the CONDATA= data set. The default domain is [0,$\infty $].

DPR= n

specifies an upper bound on the number of dead ends that are permitted before PROC CLP restarts or terminates the search, depending on whether or not a randomized search strategy is used. In the case of a nonrandomized strategy, n is an upper bound on the number of allowable dead ends before terminating. In the case of a randomized strategy, n is an upper bound on the number of allowable dead ends before restarting the search. The DPR= option has priority over the DM= option.

EVALVARSEL <=(keyword(s))>

evaluates specified variable selection strategies by attempting to find a solution with each strategy. You can specify any combination of valid variable selection strategies in a space-delimited list enclosed in parentheses. If you do not specify a list, all available strategies are evaluated in alphabetical order, except that the default strategy is evaluated first. Descriptions of the available selection strategies are provided in the discussion of the VARSELECT= option.

When the EVALVARSEL= option is in effect, the MAXTIME= option must also be specified. By default, the value specified for the MAXTIME= option is used as the maximum solution time for each variable selection strategy. When the DECRMAXTIME option is specified and a solution has been found, the value of the MAXTIME= option is set to the solution time of the last solution.

After the CLP procedure has attempted to find a solution with a particular strategy, it proceeds to the next strategy in the list. For this reason, the VARSELECT= , ALLSOLNS , and MAXSOLNS= options are ignored when the EVALVARSEL= option is in effect. All solutions found during the evaluation process are saved in the output data set specified by the OUT= option.

The macro variable _ORCLPEVS_ provides more information that is related to the evaluation of each variable selection strategy. The fastest variable selection strategy is indicated in the macro variable _ORCLP_ , provided that either at least one solution is found or the problem is found to be infeasible. See Macro Variable _ORCLP_ for more information about the _ORCLP_ macro variable; see Macro Variable _ORCLPEVS_ for more information about the _ORCLPEVS_ macro variable.

FINDALLSOLNS
ALLSOLNS
FINDALL

attempts to find all possible solutions to the CSP. When a randomized search strategy is used, it is possible to rediscover the same solution and end up with multiple instances of the same solution. This is currently the case when you are solving a scheduling CSP. Therefore, this option is ignored when you are solving a scheduling CSP.

MAXSOLNS= n

specifies the number of solution attempts to be generated for the CSP. The default value is 1. It is important to note, especially in the context of randomized strategies, that an attempt could result in no solution, given the current controls on the search mechanism, such as the number of restarts and the number of dead ends permitted. As a result, the total number of solutions found might not match the MAXSOLNS= parameter.

MAXTIME= n

specifies an upper bound on the number of seconds that are allocated for solving the problem. The type of time, either CPU time or real time, is determined by the value of the TIMETYPE= option. The default type is CPU time. The time specified by the MAXTIME= option is checked only once at the end of each iteration. Therefore, the actual running time can be longer than that specified by the MAXTIME= option. The difference depends on how long the last iteration takes. The default value of MAXTIME= is $\infty $. If you do not specify this option, the procedure does not stop based on the amount of time elapsed.

NOPREPROCESS

suppresses any preprocessing that would typically be performed for the problem.

OUT= SAS-data-set

identifies the output data set that contains one or more solutions to a standard CSP, if one exists. Each observation in the OUT= data set corresponds to a solution of the CSP. The number of solutions that are generated can be controlled using the MAXSOLNS= option in the PROC CLP statement.

PREPROCESS

permits any preprocessing that would typically be performed for the problem.

RESDATA= SAS-data-set
RESIN=SAS-data-set

identifies the input data set that defines the resources and their attributes such as capacity and resource pool membership. This information can be used in lieu of, or in combination with, the RESOURCE statement.

RESTARTS= n

specifies the number of restarts of the randomized search technique before terminating the procedure. The default value is 3.

SCHEDRES= SAS-data-set

identifies the output data set that contains the solutions to scheduling CSPs. This data set contains the resource assignments of activities.

SCHEDTIME= SAS-data-set

identifies the output data set that contains the solutions to scheduling CSPs. This data set contains the time assignments of activities.

SCHEDULE= SAS-data-set
SCHEDOUT=SAS-data-set

identifies the output data set that contains the solutions to a scheduling CSP, if any exist. This data set contains both the time and resource assignment information. There are two types of observations identified by the value of the OBSTYPE variable: observation with OBSTYPE= "TIME" corresponds to time assignment, and observation with OBSTYPE= "RESOURCE" corresponds to resource assignment. The maximum number of solutions can be controlled by using the MAXSOLNS= option in the PROC CLP statement.

SHOWPROGRESS

prints a message to the log whenever a solution has been found. When a randomized strategy is used, the number of restarts and dead ends that were required are also printed to the log.

TIMETYPE= CPU $\mid $ REAL

specifies whether CPU time or real time is used for the MAXTIME= option and the macro variables in a PROC CLP call. The default value of this option is CPU.

USECONDATAVARS= 0 $\mid $ 1

specifies whether the numeric variables in the CONDATA= data set, with the exception of any reserved variables, are implicitly defined or not. A value of 1 indicates they are implicitly defined, in which case a VARIABLE statement is not necessary to define the variables in the data set. The default value is 0. Currently, _RHS_ is the only reserved numeric variable.

VARASSIGN= MAX $\mid $ MIN

specifies the value selection strategy. Currently, there are two value selection strategies:

  • MAX, which selects the maximum value from the domain of the selected variable

  • MIN, which selects the minimum value from the domain of the selected variable

The default value selection strategy is MIN. To assign activities, use the ACTASSIGN= option in the SCHEDULE statement.

VARSELECT= keyword

specifies the variable selection strategy. The strategy could be static, dynamic or conflict-directed. Typically, static strategies exploit information about the initial state of the search, whereas dynamic strategies exploit information about the current state of the search process. Conflict-directed strategies are strategies which exploit information from previous states of the search process as well as the current state (Boussemart et al. 2004)

Static strategies are as follows:

  • FIFO, which uses the first-in-first-out ordering of the variables as encountered by the procedure

  • MAXCS, which selects the variable with the maximum number of constraints (degree)

Dynamic strategies are as follows:

  • DOMDDEG, which selects the variable with the smallest ratio of domain size by dynamic degree

  • DOMDEG, which selects the variable with the smallest ratio of domain size by degree

  • MAXC, which selects the variable with the largest number of active constraints (dynamic degree)

  • MINR, which selects the variable with the smallest range (that is, the minimum value of upper bound minus lower bound)

  • MINRMAXC, which selects the variable with the smallest range, breaking ties by selecting one with the largest number of active constraints

Conflict-directed strategies are as follows:

  • DOMWDEG, which selects the variable with the smallest ratio of domain size by weighted degree

  • WDEG, which selects the variable with the largest weighted degree

The dynamic strategies embody the "fail first principle" (FFP) of Haralick and Elliott (1980), which suggests that "To succeed, try first where you are most likely to fail." The degree of a variable is the number of constraints in which the variable appears. The dynamic degree of a variable is the degree of the variable with respect to the current set of active constraints. Boussemart et al. (2004) introduced the concept of weighted degree, which takes into account dead ends during searches. Weights are associated with constraints and variables. The weight of a constraint is initially set to 1 and incremented each time the constraint is responsible for a dead end. The weight of a variable is equal to the sum of the weights of the active constraints that it is associated with. The default variable selection strategy is MINR. To set the strategy for selecting activities, use the ACTSELECT= option in the SCHEDULE statement.