Optimization¶

This page documents the native optimization capabilities of the constraint handler. While optimization can also be modeled using standard ASP techniques, the constraint handler aims to provide a more convenient and efficient way to express optimization problems.

Maximize Sum¶

Declaration Label Support

The optimization module supports maximizing the sum of a set of Expressions. This is done using the optimize_maximizeSum predicate, which is available in multiple forms.

The predicate is available in the following forms:

optimize_maximizeSum(Expression, Id).
optimize_maximizeSum(Expression, Id, Priority).
optimize_maximizeSum(Label, Expression, Id, Priority).

The shorter forms are shorthands. The optimize_maximizeSum/2 form uses priority 0, and the optimize_maximizeSum/3 form uses an anonymous Label.

optimize_maximizeSum(Expression, Id, Priority)

Name	Description
`Expression`	The expression whose value is used in the maximization.
`Id`	Identifier for one optimization contribution. For a single aggregate value, a fixed identifier like `total` is sufficient. For multiple contributions, this is typically the item or variable identifier.
`Priority`	The priority level for this optimization criterion. Higher priorities are optimized first.

If you need to address a specific optimization declaration via requestEngine or want it to appear with an explicit label in warnings, use the optimize_maximizeSum/4 form with a leading Label.

Output¶

Result

Optimization declarations also extend the final model with additional optimize_value/3 atoms. All optimize_maximizeSum contributions that share the same Label and Priority are summed, and the aggregated total is emitted as:

optimize_value(Label, Priority, Total)

Here, Total is a regular val/2 term using the resulting numeric type, for example val(int,23) or val(float,float("8.5")).

This means that optimization labels are not just annotations for declarations. They also become observable result symbols in the final model.

When clingo continues enumerating optimal models in combination with brave or cautious reasoning, the constraint handler freezes these optimize_value/3 atoms at the first model whose optimality_proven flag is true and reuses that same valuation for later models in the same solve call. This is intentional, to give you access to partial information about the optimality criteria. These are not the consequences!

Note

The shorthand forms optimize_maximizeSum/2 and optimize_maximizeSum/3 use the anonymous label _label_anonymous. As a consequence, they also produce a result atom of the form optimize_value(_label_anonymous, Priority, Total). If you want a stable and meaningful output atom, use the explicit optimize_maximizeSum/4 form with your own label.

Single Value¶

When wanting to optimize over a single value, the result could be captured in a Variable which is then optimized using the optimize_maximizeSum/2 or optimize_maximizeSum/3 predicate directly. Here, single value doesn't mean the result has to be based on a single variable, just that the result can be captured in a single Expression.

Example 1: Optimization Over a Single Variable

Consider a program that defines the variables x with a single value between 1 and 10.

1{variable_define(x, val(int, 1..10))}1.

The variable x can then be maximized using:

optimize_maximizeSum(variable(x), total, 0).

The result will be the model where x takes the value 10.

value(x,val(int,10))

Example 2: Optimization Over Multiple Variables

Consider a program that defines two variables x and y, each with values between 1 and 10.

1{variable_define(x, val(int, 1..10))}1.
1{variable_define(y, val(int, 1..10))}1.

The sum of the variables x and y can then be maximized using:

optimize_maximizeSum(operation(add, (variable(x),(variable(y),()))), total, 0).

The result will be the model where both x and y take the value 10, maximizing their sum to 20.

value(x,val(int,10))
value(y,val(int,10))

Multiple Values¶

Sometimes, the exact number of Variables is unknown or represents the optimization target itself. In these cases, the optimization can be expressed using multimaps to capture all Values that should be optimized over.

Example 3: Optimization Over Multiple Values

Consider a program that defines some items as follows:

item(a,2).
item(b,4).
item(c,-1).

Here, each item has some identifier and a value.

To let the program freely select any set of items, we use a choice rule together with a multimap to declare items as taken:

multimap_declare(taken).
{ multimap_assign(taken,val(symbol,X),val(int,V)) } :- item(X,V).

We can now optimize the selection such that we get the highest possible sum of values as follows:

optimize_maximizeSum(EXPR,X,0) :- item(X,V),
    ITEM = val(symbol,X),
    COND = operation(multimap_isin,(ITEM,(variable(taken),()))),
    VALU = val(int,V),
    EXPR = operation(if,(COND,(VALU,()))).

The result will be the model where items a and b are taken, maximizing the sum to 6. Because this example uses the anonymous label, the optimization summary also appears as optimize_value(_label_anonymous,0,val(int,6)).

multimap_value(taken,val(symbol,a),val(int,2))
multimap_value(taken,val(symbol,b),val(int,4))
optimize_value(_label_anonymous,0,val(int,6))

Example 4: Optimization with Priorities

Priorities allow you to specify multiple optimization criteria where higher-priority goals are optimized first. Consider a program with two criteria: maximizing value (priority 1) and minimizing weight (priority 0).

capacity(11).
item(a,6,12).
item(b,3,10).
item(c,4,11).
item(d,5,11).

multimap_declare(taken).
{ multimap_assign(taken,val(symbol,X),val(int,W)) } :- item(X,W,V).

% Maximize value with priority 1 (higher priority)
optimize_maximizeSum(EXPR,X,1) :- item(X,W,V),
    ITEM = val(symbol,X),
    COND = operation(multimap_isin,(ITEM,(variable(taken),()))),
    VALU = val(int,V),
    EXPR = operation(if,(COND,(VALU,()))).

% Minimize weight with priority 0 (lower priority) by maximizing negative weight
optimize_maximizeSum(EXPR,X,0) :- item(X,W,V),
    ITEM = val(symbol,X),
    COND = operation(multimap_isin,(ITEM,(variable(taken),()))),
    WGHT = val(int,-W),  % Negate weight to minimize it
    EXPR = operation(if,(COND,(WGHT,()))).

variable_define(carried,EXPR) :-
    EXPR = operation(multimap_fold,(LAMB,(MAP,(STAR,())))),
    MAP  = variable(taken),
    ACCU = variable(accu),
    STAR = val(int,0),
    VARS = (w,(accu,())),
    WEIG = variable(w),
    PLUS = operation(add,(WEIG,(ACCU,()))),
    LAMB = lambda(VARS,PLUS).

ensure(operation(leq,(variable(carried),(val(int,C),())))) :- capacity(C).

The solver will first maximize value (priority 1), and among solutions with equal value, it will minimize weight (priority 0). This corresponds to the model where items a and c are taken. Since both declarations use the anonymous label, the model also contains aggregated optimization totals for each priority under _label_anonymous.

multimap_value(taken,val(symbol,a),val(int,6))
multimap_value(taken,val(symbol,c),val(int,4))
optimize_value(_label_anonymous,1,val(int,23))
optimize_value(_label_anonymous,0,val(int,-10))

Precision¶

Declaration

By default, the optimization module uses a precision of 1 for floating-point calculations. This can be adjusted using the optimize_precision/2 predicate.

optimize_precision(Precision, Priority)

Name	Description
`Precision`	The Value to be used for floating-point calculations. Must be a positive Int.
`Priority`	The priority level for which to set the precision.

For convenience, there also exists a shorthand version optimize_precision/1 where the precision applies to all priorities that don't have a specific precision set.

Example

Given the following variable x with a set of possible Float values:

variable_declare(x, fromFacts).
variable_domain(x, val(float, float("-2.239"))).
variable_domain(x, val(float, float("-2.235"))).
variable_domain(x, val(float, float("-2.21"))).
variable_domain(x, val(float, float("-2.1"))).
variable_domain(x, val(float, float("-1.0"))).
variable_domain(x, val(float, float("4.0"))).
variable_domain(x, val(float, float("5.0"))).

Assuming optimization for the lowest possible value without setting any precision:

optimize_maximizeSum(operation(mult,(variable(x),(val(int, -1),()))), total, 0).

Because the default precision is 1, this would yield all models containing the floats starting with -2. as optimal models.

Increasing the precision to 100

optimize_precision(val(int,100)).

would yield only the models containing -2.239 and -2.235 as optimal models.

The precision could be increased to 1000

optimize_precision(val(int,1000)).

to yield the single optimal model containing only -2.239 as a result.