2 The General Model and its Operators

A optimization problem can be formulated as follows:

min        f(x)

subjectto  gi(x ) ≤ 0   forall i ∈ {1,...,m }
           x ∈ X

where f, gi are functions defined in n (or n), X is a subset of n (or n), and x is a vector of n components x1,,xn (see [14]). The notation formalism is given in [12].

Commonly, the functions f, gi are mathematical functions that consist of the usual operands and operators: numbers, variables, parameters and the operators for addition, subtraction, etc., and also function like sin, log etc. f(x) is a function that results in a numerical value. The constraints, however, are Boolean expressions: gi(x) 0 that are true or false. Of course, gi(x) also results in a numerical value which is smaller or equal zero (which means that the constraint holds (is true), otherwise it does not hold (it is false).

Let us now extend the syntax of the general optimization model: besides the usual operands (numbers, parameters, variables) and numerical operators in a constraint, Boolean propositions, and predicates as well as Boolean operators can be used. This allows one to mix logical and mathematical notation in one single expressions. In order to make sense for all such expressions, we introduce the convention that the two basic value in logic (false and true) are mapped to the two numerical values: zero and not-zero (respectively one), this is also common practice in some programming languages. Hence, we adopt the convention for a Boolean proposition x that “x = 0” means “x is false” and in all other cases “x is true” (in particular when “x = 1”). The generalization of a mathematical-logical model is then as follows:

min        F(x )
subjectto  Gi(x)   forall i ∈ {1, ...,m }
           x ∈ ℕn(orℝn )

where F(x) and Gi(x) are expressions containing mathematical and logical operators. This is a powerful way to compactly specify a large variations of constraints in a uniformed syntax. Before using them in concrete model, these operators and their precedence within an expression is now defined. All the operators and operands that are allowed in a constraint are listed in Table 1, x and y are arbitrary (sub)-expressions. The precedence is in decreasing order within the table. Indexed operators are listed in Table 2. The indexed operators all have the same precedence.

Operation LPL syntax meaning

+(-)x +x unary plus (minus)
x (x) ~x Boolean negation
(x) (x) nesting, changing precedence

xy x^y x power y (x 0)
x mod y x%y x modulo y
min(x,y) Min(x,y) the smaller of x and y
max(x,y) Max(x,y) the larger of x and y
x∕y x/y division
xy x*y multiplication
x - y x-y substraction
x + y x+y addition
f(x) f(x) function like sin(x) etc.

x y x>=y greater or equal
x y x<=y less or equal
x > y x>y greater
x < y x<y less
x = y x=y equal
x = y x<>y not equal
x y x and y Boolean AND
x y x or y Boolean OR
x˙∨y x xor y Boolean exclusive-OR
x y x <-> y Boolean equivalence
x y x -> y Boolean implication
x y x <- y Boolean reverse implication
x y x nand y Boolean NAND
x y x nor y Boolean NOR
x := y x := y assignment (returns x)
x,y x , y list operator

Table 1: Operators and operands in an expression

symbol LPL syntax meaning

ixi sum{i} x summation
ixi prod{i} x product
min ixi min{i} x smallest value
max ixi max{i} x largest value
argminixi argmin{i} x index of the smallest value
argmaxixi argmax{i} x index of the largest value
if(x,y,z) if(x,y,z) returns y if x is true else z
ixi forall{i} x indexed Boolean AND
ixi and{i} x indexed Boolean AND
ixi exist{i} x indexed Boolean OR
ixi or{i} x indexed Boolean OR
∨˙ixi xor{i} x indexed Boolean XOR
ixi nand{i} x indexed Boolean NAND
ixi nor{i} x indexed Boolean NOR
atleast(k)i xi atleast(k){i} x at least k must be true
atmost(k)i xi atmost(k){i} x at most k must be true
exactly(k)i xi exactly{i} x exactly k must be true

Table 2: Indexed Operators in an expression

Three examples that corresponds to a syntactical correct expression are given:

  1. “If x and y are true or z is true then and only then w is false”. This is a purely Boolean expression formulated as:

    x ∧ y ∨ z ˙∨ w
  2. “If a is smaller or equal than b or if 3b is the same as 4c then x or y or both must be true”. This is a mixed expression containing mathematical and logical operators formulated as:

    (a ≤ b ∨  3b = 4c) →  (x ∨ y )
  3. Let i I be a set, Pi be an array of Boolean propositions, and N als be a Boolean proposition that can be true or false. We have the statement: “At most 3 out of all Pi are true or N and exactly one Pi is true, with i I”. This is an expression with indexed operators formulated as:

atmost(3)i Pi ∨ (N ∧   iPi)

The third expression above may occur in a production planning context. Let Pi be the proposition that “product i is manufactured” and let N be the proposition that “most machines (say at least 80%) are maintained”. Then the constraint may be interpreted as: “At most 3 different products can be manufactured or exactly one product must be manufactured when most machines are maintained (N)”.

The definition of the various Boolean operations is given in Table 3.

x y x y x y x∨˙y x y x y x y x nand y x nor y

1 1 1 1 0 1 1 1 0 0
1 0 0 1 1 0 0 1 1 0
0 1 0 1 1 1 0 0 1 0
0 0 0 0 0 1 1 1 1 1

Table 3: The Boolean Operators