In an Extended Backus-Naur Form (EBNF) type of style, the following grammar specifies the syntax of a linear program:
| Non-terminal |
|
Rule |
Description |
symbol |
= |
<any symbol> ; |
|
eol |
= |
<end of line> ; |
any of the sequences '\n' (Linux), '\r\n' (Windows) or '\r' (Mac) |
eop |
= |
<end of program> ; |
|
space |
= |
" " ; |
|
|
| Delimiters |
|
|
according to settings by user |
decimal point |
= |
"." ; |
International style |
thousands separator |
= |
"," ; |
decimal point |
= |
"," ; |
German style |
thousands separator |
= |
"." ; |
spaces |
= |
space , { space } ; |
|
blockComment |
= |
"/*" , { symbol } , "*/" ; |
cannot be processed across multiple lines |
eolComment |
= |
"#" , { symbol } , eol ; |
";" within eolComments will not be processed |
comment |
= |
{ space } , ( blockComment | eolComment ) ; |
|
vComment |
= |
{ space } , ( [ blockComment ] | line break ) , { space } ; |
optional comments in between a variable or line break within a line |
line break |
= |
( line | objective | constraint ) , "\" , eol ; |
add multiple lines logically together, line break can be entered within any line at any point |
delimiter |
= |
spaces | ( { space } , "," , { space } ) | ";" | "\t" | ( { space } , [ ( "+" | "-" ) ] , { space } ) | blockComment | line break ; |
International Settings |
delimiter |
= |
spaces | ( spaces , "," , spaces ) | ";" | "\t" | ( { space } , [ ( "+" | "-" ) ] , { space } ) | blockComment | line break ; |
German Settings |
|
| Basics |
|
|
according to upload by user |
sign |
= |
{ space } , ( "+" | "-" ) ; |
+ indicates a non-negative domain (≥ 0)
- indicates a non-positive domain (≤ 0) |
digit |
= |
"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; |
|
number block |
= |
[ thousands separator ] , digit , digit , digit ; |
an optional thousands separator may be used to structure numbers in groups of three digits |
integer |
= |
[ "-" , { space } ] , [ [ digit ] , digit ] , digit , { number block } ; |
float number |
= |
integer | ( integer , decimal point , { digit } ) | ( [ integer ] , digit , { digit } ) ; |
3. or .4 are feasible, 0. or .0 are equivalent to 0 |
rational number |
= |
float number , [ "/" , float number ] ; |
a number can be a fraction of two float numbers |
name |
= |
symbol , { symbol } ; |
name has to start with a letter; if no name is given, numbers beginning with 1 will take that place to declare constraints; objective can also have a name |
lp offset |
= |
{ space } , rational number , { space } ; |
does not change the lp solution, but will change the final objective value |
|
| Limits |
|
|
according to upload by user |
equality |
= |
"=" , { space } , rational number ; |
|
lower limit |
= |
">=" , { space } , rational number ; |
lower bound of a variable |
upper limit |
= |
"<=" , { space } , rational number ; |
upper bound of a variable; N<=1 or Z+<=1 is equivalent to B |
OR ZERO |
= |
{space } , "|0" ; |
semi-continuous variable that may take either the value 0 or values within given limits; should only be used with limits |
limits |
= |
( ( lower limit , [ { space } , upper limit ] ) | ( upper limit , [ { space } , lower limit ] ) ) , [ OR ZERO ] ; |
both a lower and an upper limit may be specified; the order is up to the user; also semi-continuous limits possible |
|
| Variables |
|
|
|
variable type |
= |
"B" | "N" | ( "Z" , [ sign ] ) | ( "R" , [ sign ] ) ; |
B indicates a binary variable (∈ {0; 1})
N indicates a natural variable including 0 (∈ ℕ0)
Z indicates an integer variable (∈ ℤ); Z+ is equivalent to N
R indicates an integer variable (∈ ℝ);
if no variable type is given, R+ is assumed,
if only + or - is given, R+ or R-, respectively, is assumed. |
variable domain |
= |
"[" , { space } , [ variable type ] , { space } , [ limits ] , { space } , "]" ; |
a variable domain is encapsulated within [ ... ] |
variable |
= |
vComment , rational number , vComment , { symbol } , vComment , [ variable domain ] , vComment ; |
objective comments (left-hand side) will be assigned to certain variables, Note: constraint comments (left-hand side) are feasible but will not be processed |
variables |
= |
variable , { delimiter , variable } ; |
|
|
| Grammar |
|
|
|
max |
= |
"M" | "m" , "A" | "a" , "X" | "x" ; |
upper or lower case does not interfere with solvability |
min |
= |
"M" | "m" , "I" | "i" , "N" | "n" ; |
upper or lower case does not interfere with solvability |
description |
= |
( name , spaces , [ lp offset ] ) | ( lp offset , spaces , [ name ] ) |
name has to start with a letter; if no name is given, numbers beginning with 1 will take that place to declare constraints |
objective |
= |
variables , "->" , vComment , ( max | min ) , vComment , [ variable domain ] , vComment , [ description ] , [ comment ] ; |
objective function is not required |
constraint |
= |
variables , ( lower limit | upper limit | equality ) , vComment , rational number , [ comment ] ; |
lp with only constraints will be solved without objective condition ??? |
SOS |
= |
variables , "CS" , { space } , [ rational number | ( rational number , ":" , rational number ) ] , [ name ] ; |
special ordered sets ; default value is 1, but any rational number or even ranges are feasible |
line |
= |
vComment | ( [ vComment ] , eolComment ) | <empty line> ; |
|
lp |
= |
{ line } , [ objective ] , { line } , ( constraint | SOS ) , { [ line ] , ( constraint | SOS ) } , { line } , eop ; |
if objective is used, it has to be declared before the constraints |
