Specifications PyCSP³ Tools Instances Competitions About

Objectives

There are two kinds of elements that can be used for representing objectives. You can use:

an element minimize
or an element maximize

These elements must be put inside objectives. The role of the attribute combination is explained later.

Syntax

<objectives  [ combination="combinationType" ]>
  (<minimize.../> | <maximize.../>)+ 
</objectives>

Each element minimize and maximize has an optional attribute id and an optional attribute type, whose value can currently be:

expression
sum
product
minimum
maximum
nValues
lex

For XCSP³core, we only consider mono-objective optimization.

Objectives in Functional Forms

The default value for type is expression, meaning that the content of the element minimize or maximize is necessarily a numerical functional expression (of course, possibly just a variable) built from operators described in the Table introduced for constraint intension.

An objective in functional form is thus defined by an element minimize or maximize. We only give the syntax of minimize (as the syntax for maximize is quite similar) for COP instances. Here, an integer functional expression is referred to as intExpr in the syntax box below; its precise syntax is given in the Syntax page.

Syntax

<minimize  [ id="identifier" ]  [ type="expression" ]>
  intExpr
</minimize>

An example is given below for an objective that consists in minimizing the value of the variable z, and an objective that consists in maximizing the value of the expression x+2y.

Example

<minimize> z </minimize>
<maximize> add(x,mul(y,2)) </maximize>

This way of representing objectives is generic, but when possible, it is better to use specialized forms in order to simplify the XCSP³ code and also to inform directly solvers of the nature of the objective(s).

Objectives in Specialized Forms

Whatever is the type among sum, product, minimum, maximum, nValues and lex, two forms are possible. We show this for the element minimize, but of course, this is quite similar for the element maximize. Here, we give the syntax for COP instances:

Syntax

<minimize  [ id="identifier" ]  type="sum|product|minimum|maximum|nValues|lex">
  <list> (intVar wspace)2+ </list>
  [<coeffs> (intVal wspace)2+ </coeffs>]
</minimize>

There is one possible coefficient per variable. When the element coeffs is absent, coefficients are all assumed to be equal to 1, and the opening/closing tags for list become optional, which gives:

Syntax

 <minimize  [ id="identifier" ]  type="sum|product|minimum|maximum|nValues|lex">
        (intVar wspace)2+  <!-- Simplified Form -->
</minimize>

For the semantics, we consider that $X=\langle x_1,x_2,\ldots,x_k\rangle$ and $C=\langle c_1,c_2,\ldots,c_k\rangle$ denote the lists of variables and coefficients. Also, minimize$_{lex}$ denotes minimization over tuples when considering the lexicographic order. Finally, the type is given as third argument of elements minimize below.

minimize(X,C,sum)	minimize {$\sum_{i = 1}^{\|X\|} c_i \times x_i$}
minimize(X,C,product)	minimize {$\prod_{i = 1}^{\|X\|} c_i \times x_i$}
minimize(X,C,minimum)	minimize {$\min_{i = 1}^{\|X\|} c_i \times x_i$}
minimize(X,C,maximum)	minimize {$\max_{i = 1}^{\|X\|} c_i \times x_i$}
minimize(X,C,nValues)	minimize {$\|\{c_i \times x_i : 1 \leq i \leq \|X\|\}\|$}
minimize(X,C,lex)	{minimize$_{lex}$ $\langle c_1 \times x_1, c_2 \times x_2, \ldots, c_k \times x_k \rangle$}

The following example shows an objective that consists in minimizing $2x_1 + 4x_2 + x_3 + 4x_4 +8x_5$, and an objective that consists in minimizing the highest value among those taken by variables y1,y2,y3,y4.

Example

<minimize type="sum"> 
  <list> x1 x2 x3 x4 x5 </list> 
  <coeffs> 2 4 1 4 8 </coeffs>
</minimize>
<minimize type="maximum"> 
  <list> y1 y2 y3 y4 </list> 
</minimize>

Because the opening and closing tags of list are optional here (as there is no element coeffs, the second objective above can be simply written:

Example

<minimize type="maximum"> y1 y2 y3 y4 </minimize>

There is no real interest in introducing coefficients for product.