This page gives an overview of the LP format. A formal definition of the LP format syntax can be found in LP format BNF definition. For a detailed discussion of what constitutes a legal LP token see LP format tokens. The rules by which QSopt defines a variable's bounds in the absence of explicit bound definitions are found in Default variable bounds.
The LP-format example below defines a linear-programming problem called smallExample. The example's objective section defines the objective obj to be x - 2.3y + 0.5z, where x and y, and z are variables. The problem's objective is to maximize the given linear expression. The constraint section contains two constraints. The first constraint, called c1, states that x - y + s must be less than or equal to 10.75. The the second constraint states that -z + 2x - s must be greater than or equal to -100. The QSopt parser will create a name for the second unnamed constraint.
Problem
smallExample
Maximize
obj: x - 2.3y + 0.5z
Subject
c1: x - y + s <= 10.75
-z + 2x - s >= -100
End
The objective function in an LP-format description may be empty, that is, it
may contain no terms; in such a case, the optimization routines attempt only to
find a feasible solution when solving the problem.
Constraints may be empty as well; empty constraints are simply ignored. Constraints must always contain a right-hand-side, that is a comparison operator and a number. QSopt parses the unnamed constraint
<= -1000
correctly but ignores it because it contains no terms.
The bounds section is used to define variable bounds that differ from the defaults assumed by the QSopt parser, see Default variable bounds . The lines
Bounds
x <= 10.5
y <= -1
-10 <= z <= 100
s = 1.0
state that x ranges from 0 to 10.5, y ranges from negative infinity to -1, z
ranges from -10 to 100, and s is fixed at 1.
To define a variable x's range to be unbounded its lower and upper bound must either be explicitly given as
-inf<=x<=inf
or alternatively as
x free
where free, -inf, and inf are keywords.
Note that there need not be white space between -inf, inf, and x and the <= operators, because identifiers and keywords never contain '<' or '=' characters. On the other hand, if there were no space between x and free, xfree would be interpreted to be an unknown column name, since the variable xfree is used nowhere else in the LP problem statement.
To fix a variable to a specific value, its lower and upper bound must be set to the same value. This can be achieved in two ways:
y = 10.1
10.0 <= x <= 10.0
By default variables may assume any floating point value within their bounds. If a variable is restricted to integer values (a MIP problem), then it must be listed in the integer section. The lines
Integer
x y
state that the variables x and y are required to take on integer values only.
Integer variables are binary in the absence of explicit lower or upper bound
definitions, that is, they represent the values 0 or 1.
All LP format keywords must appear at the beginning of a line. Identifiers used to name constraints and variables are sequences of the characters (0-9), (a-z), (A-Z), and !"#$%&()/,;?@_`'{}|~. They may not start with a period (.). Comments are introduced by the character '\'. The LP format parser ignores all text after '\' until the end of the line.
Tokens may be separated by white space, that is by blanks, tabs, newlines, formfeeds, and control-returns. The LP format parser always tries to match the longest possible string to the next token. Therefore, two tokens must be separated by white space from each other in an LP-format description if their combination becomes a legal token itself. For example, writing
Bounds
10<=xy<=10 \ x and y glued together
is interpreted as 10 <= xy <= 10 and not as 10 <= x, y <= 10.
It is legal to use as constraint or variable names the same strings that are used for keywords such as ST, integer, or Bound. If these strings appear at the beginning of a line they are always interpreted as keywords. When using variables and constraint names that look like keywords, LP-format descriptions quickly become very confusing and it is strongly recommended not to do so. Consider the following example, where the objective is to maximize the variable ST under the constraint that ST is less than or equal to 10.
MAX
ST
ST
ST <= 10
END
The LP format parser is able to interpret the LP problem as intended, since the
first ST is not placed at the beginning of its line and is therefore
recognized as an identifier. The second ST starts a line and is
recognized as the keyword that starts the constraint section and the third ST
becomes the term of the problem's constraint. If the first or third ST is
moved to the start of its line, then the LP-format description becomes
incorrect.