A optimization problem can be formulated as follows:
where f, g_{i} are functions defined in ℝ^{n} (or ℕ^{n}), X is a subset of ℝ^{n} (or ℕ^{n}), and x is a vector of n components x_{1},…,x_{n} (see [14]). The notation formalism is given in [12].
Commonly, the functions f, g_{i} 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: g_{i}(x) ≤ 0 that are true or false. Of course, g_{i}(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:
where F(x) and G_{i}(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 |
x^{y} | 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 |
xy | 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 |
symbol | LPL syntax | meaning |
∑ _{i}x_{i} | sum{i} x | summation |
∏ _{i}x_{i} | prod{i} x | product |
min _{i}x_{i} | min{i} x | smallest value |
max _{i}x_{i} | max{i} x | largest value |
argmin_{i}x_{i} | argmin{i} x | index of the smallest value |
argmax_{i}x_{i} | argmax{i} x | index of the largest value |
if(x,y,z) | if(x,y,z) | returns y if x is true else z |
∀_{i}x_{i} | forall{i} x | indexed Boolean AND |
∧ _{i}x_{i} | and{i} x | indexed Boolean AND |
∃_{i}x_{i} | exist{i} x | indexed Boolean OR |
∨ _{i}x_{i} | or{i} x | indexed Boolean OR |
_{i}x_{i} | xor{i} x | indexed Boolean XOR |
¬∧ _{i}x_{i} | nand{i} x | indexed Boolean NAND |
¬∨ _{i}x_{i} | nor{i} x | indexed Boolean NOR |
atleast(k)i x_{i} | atleast(k){i} x | at least k must be true |
atmost(k)i x_{i} | atmost(k){i} x | at most k must be true |
exactly(k)i x_{i} | exactly{i} x | exactly k must be true |
Three examples that corresponds to a syntactical correct expression are given:
“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:
“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:
Let i ∈ I be a set, P_{i} 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 P_{i} are true or N and exactly one P_{i} is true, with i ∈ I”. This is an expression with indexed operators formulated as:
The third expression above may occur in a production planning context. Let P_{i} 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.