Constraint Programming

The Constraint Programming task calculates the optimal solution by providing the input file containing both data and the constraints, modeled as a collection of decision variables, each one associated with a domain of possible values, together with a set of constraints that specify which combinations of values are admissible.

The Input Dataset

The Constraint Programming task requires the input dataset to be organized in a specific tabular format, where every row defines either a decision variable or a constraint of the model.

The dataset is made of seven cols:

Column

Description

Row

Identifies the role of the row (see Row roles below). All the rows belonging to the same variable or constraint share the same value in this column, when its value is greater than 0.

Col

Contains the incremental, 1-based identifier of a variable. This value is populated only in rows defining a variable, and it is left empty in rows defining a constraint.

Value

Contains a numeric value, whose meaning depends on the Row, Function and ArgCol columns (see below).

Function

Contains the name of the function used to define a variable or a constraint. It can be left empty, meaning that the row defines a plain (base) variable.

ArgPos

Contains the 1-based position, within the function specified in Function, of the argument being defined by the row.

ArgCol

Contains the identifier (as defined in the Col column) of the variable used as the argument in position ArgPos of the function.

Name

Contains a unique label identifying the variable or the constraint defined by the row.

Row roles

The value contained in the Row column determines whether the corresponding line of the dataset defines a variable or a constraint:

  • Row = 0: the row defines a new variable of the model. The variable is identified by the value of the Col column.

  • Row > 0: the row defines a constraint of the model. The value of Row is the incremental identifier of the constraint. In this case, the Col column must be left empty.

  • Row (empty): the variable defined in Col is used as cost of the problem. Multiple objectives are ordered according to the value of ArgPos.

  • Row = -1: the row defines the maximum value of the variable identified by Col. The maximum value is specified in the Value column.

  • Row = -2: the row defines the minimum value of the variable identified by Col. The minimum value is specified in the Value column.

Note

Additional roles of the Row column, used to specify a variable’s minimum value, maximum value or cost coefficient, are described together with the corresponding options in The Options tab below.

Defining a variable’s domain

On a row with Row = 0 (i.e. a row defining a variable), if the Function column is left empty, the Value column specifies the domain of the variable:

  • 0: the variable is continuous.

  • 1: the variable is integer.

  • 2: the variable is boolean.

If, instead, the Function column is not empty, the variable is not a plain scalar, but it is defined through one of the available functions (for example interval or set, list, permutation): in this case the row, along with the following rows sharing the same Col value and the same Function value, follows the same function/argument mechanism described below for constraints.

Defining constraints and function arguments

Every constraint (as well as every variable defined through a function, see above) is modeled by one or more consecutive rows: one row for each argument required by the function. All these rows share the same Row value (or the same Col value, for functionally-defined variables) and the same Function value.

For each of these rows:

  • Function contains the name of the function (see Function families below).

  • ArgPos contains the 1-based position of the argument being defined, among the arguments accepted by Function.

  • ArgCol contains the identifier of the variable used as that argument.

  • Value contains the multiplicative factor applied to the variable referenced in ArgCol, for that argument.

Tip

Example: let X be the boolean variable identified by 1, and Y the variable identified by 2. The constraint \(2X \le 3Y\) is expressed with the leq function, which takes two arguments, using the two following rows:

Row

Column

Value

Function

ArgPos

ArgCol

Name

1

(empty)

2

leq

1

1

myConstraint

1

(empty)

3

leq

2

2

myConstraint

Naming variables and constraints

The Name column contains a label identifying the variable or the constraint defined by the row. This name must be unique:

  • every distinct value of the Col column (i.e. every variable) must be associated with a different Name;

  • every distinct value of the Row column greater than 0 (i.e. every constraint) must be associated with a different Name.

Function families

Variables and constraints are defined, as described above, through a set of available functions. These functions are organized into the following families:

Each family is presented in detail in a dedicated page, containing the list of functions belonging to it, together with the description of the arguments each function accepts, whether each argument is mandatory or optional, and, when relevant, the specific limitations on the accepted argument type.

Constraint Programming functions

The Constraint Programming task input dataset (see The Input Dataset) uses functions to define both the variables and the constraints of the model.

Functions are organized in families to group similar operations. Function families currently available are:

Each of these families is presented in detail in a dedicated page. Follow the links contained in the list above to get more information about the desired functions.

Note

Functions which are used to define constraints are only the functions which always return a boolean value (0 or 1). In rows with Row > 0, only these functions or the functions if and iff can be used. The other functions are used to define variables, and they can be used in rows with Row = 0.

How to read a function signature

Every function accepts one or more arguments, referred to in the following pages as Argument 1, Argument 2, and so on, according to their position.

Each argument is described by two pieces of information:

  • its type, i.e. the kind of value it accepts;

  • whether it is mandatory or optional.

Argument types

The following general types are used to describe the arguments accepted by a function:

  • numeric: any argument of type boolean, integer or continuous.

  • boolean: a boolean (0/1) argument.

  • integer: an integer argument.

  • continuous: a continuous (real) argument.

  • interval: an argument defined through the interval function.

  • collection: a list or a set or a permutation variable.

  • list / set / permutation: an argument defined through the list, set or permutation functions.

  • array: any type with a dimension greater than 0. For example, an argument described as array of integer of dimension 1 only accepts a plain array of integer values: this array cannot contain further arrays, since the whole object must have dimension 1.

  • any: no restriction is enforced on the type of the argument.

Argument dimension

The dimension of an argument describes how deeply it is nested:

  • dimension 0 means a scalar object;

  • dimension 1 means an array of scalar objects;

  • dimension 2 means an array made of arrays of scalar objects;

  • and so on for higher dimensions.

Note

The configuration of the arguments accepted by a function can depend on the dimension of its first argument. For this reason, some functions in the following pages are documented with more than one signature, one for each supported dimension of Argument 1.

Mandatory and optional arguments

Each argument of a function is either:

  • Mandatory: the argument must always be provided.

  • Optional: the argument can be omitted.

Note

Some functions accept a variadic number of arguments. This is documented by labeling the corresponding argument as Argument >= N, for some position N: any number of additional arguments (including zero) can be provided starting from that position, and, together with the previous argument(s), they are treated as the elements of a single array of dimension 1, passed as the actual operand accepted by the function.

The Options tab

The Options tab can be divided into two main areas: the constraint definition area, and the Solver area.

In the constraint definition area, the following options can be found:

  • Attribute for constraint index: select from the attribute list an integer attribute containing the row position. This field is mandatory. Specific values within the attribute have specific roles:

    • Positive values are associated to rows defining constraints. These are the variables’ indexes.

    • The value 0 is associated to rows defining variables.

    • The value -1 is associated to the rows defining the maximum value of the variable. The maximum value is in the Attribute for coefficient value attribute.

    • The value -2 is associated to the rows defining the minimum value of the variable. The minimum value is in the Attribute for coefficient value attribute.

    • Missing values are associated to the rows defining the cost of the associated variable.

  • Attribute for variable index: select from the attribute list an integer attribute. This field is mandatory. Specific values within the attribute have specific roles:

    • Missing values are associated to the rows defining constraints.

    • Positive integer values are associated to rows defining variables. These are the constraints indexes.

  • Attribute for coefficient value: select from the attribute list a numeric attribute containing the coefficient of the Attribute for argument value for rows defining variables or constraints. This field is mandatory.

  • Attribute for function value: select from the attribute list the nominal attribute containing the function name defining a constraint or a variable. This field is mandatory.

  • Attribute for argument value: select from the attribute list the integer attribute indicating the arguments of the function defining a constraint or a variable. This field is mandatory.

  • Attribute for argument position value: select from the attribute list the integer attribute, containing 1-based values, specifying the position of the corresponding argument in the corresponding function.

  • Attribute for variable name: select from the attribute list the nominal attribute containing the name of the variable. If this attribute is specified, then a name is associated to each variable’s index. Using a variable name can be useful when an error is raised by the task, as the variable name will be used in place of the variable index.

In the Solver area, the following options can be found:

  • Optimization mode: select whether you want your solution to Minimize (default) or Maximize the outcome.

  • Solver used for optimization: select from the drop-down list the solver. The only available solver is Hexaly (more information can be found here).

  • Maximum execution time (seconds): specify how many seconds the task can run. If not specified, no time limits are set.

  • Maximum number of iterations: specify how many times the task can be run. If not specified, no limits on the number of iterations are set.

  • Set an absolute gap limit: specify the limit of the absolute cost gap between the feasible solution and the optimal solution.

  • Set a relative gap limit: specify the limit of the relative cost gap between the feasible solution and the optimal solution.

  • Stop at first feasible solution: if selected, the optimization operation stops when a solution satisfying all the constraints is found. It might be possible that the solution found is not the best one.

  • Seed for the solver (negative no seed):

In the Output area, the following options can be found:

  • Add feasible column in dataset: if selected, a boolean column, called ‘Feasible’ is added to the dataset. The value True indicates that the solution is feasible, while the value False indicates that the solution is unfeasible.

  • Return the value of all defined variables: if selected, the output file will contain the values of the variables defined by one among the following functions missing, interval, at, set, list, permutation.

The Results tab

In the Results tab, results on computation are displayed. It is divided into two panels:

  • In the General Info panel, the following information can be found:

    • the Task Label

    • the Elapsed time

  • In the Result Quantities panel, the following information can be found:

    • the Number of simplex interactions made by the solver

    • the Resulting value of the cost function

    • the Status of the solver/solution

    • the Time spent by the solver to find the solution

Example

The following example is based on the Bin Packing Problem, which is an optimization problem involving packing a set of items into the fewest number of bins at a fixed capacity.

In this example, we will analyze the short version of the problem, where the input file already follows the constraints listed above, in the corresponding section.

Click here to download the extended version of the used flow, where two text files are provided, and you can use them to learn better how to describe the optimization problem.

  • Import the BinExampleInput file into the flow.

  • Add a Constraint Programming task to the flow, and configure it as follows:

    • In the Attribute for constraint index option, choose Constraint.

    • In the Attribute for variable index option, choose Variable.

    • In the Attribute for coefficient value option, choose Value.

    • In the Attribute for function value option, choose Function.

    • In the Attribute for argument value option, choose Argument.

    • In the Attribute for argument position value option, choose ArgumentPosition.

    • In the Attribute for variable name option, choose Name.

  • Leave the other options unchanged.

  • Save and compute the task.

  • Add a Data Manager task to the flow, and link it to the Constraint Programming task to visualize the results: in this case, the feasible column is left empty.