.lp format for MIPs#
Introduction#
The LP (Linear Programming) format is a widely used, human-readable format for representing optimization models. It is designed to be intuitive and easy to read, making it suitable for manual creation and editing. While it offers flexibility and readability, the LP format may not preserve certain model properties, such as variable ordering or exact numerical precision of coefficients. All files that correspond to this format must have the extension .lp in the file name.
Basic Structure#
An LP file is organized into several sections, each starting with a specific keyword. The general structure includes:
Objective Function
Constraints
Bounds
Variable Types
Special Constraints (SOS and Indicator)
End Statement
Here’s a simple example of an LP file:
\ Here is a comment line that always starts with "\"
Maximize
obj: x + y + z
Subject To
c1: x + y = 1
c2: x + 5 y + 2 z <= 10
Bounds
0 <= x <= 5
z >= 2
Generals
x y z
End
1. Objective Function#
The objective function defines what is to be maximized or minimized.
Keywords:
Minimize
,Maximize
,Min
,Max
.Structure:
Optional label (name), followed by a colon
:
.Linear expression of variables.
Optional quadratic terms enclosed in square brackets
[ ]
.
Quadratic Terms:
Use squared terms like
x^2
or cross-product terms likex * y
.Quadratic expressions are enclosed in
[
and]
and typically divided by 2 for symmetry reasons.
Example:
Minimize
obj: 3.1 x + 4.5 y + 10 z + [ x^2 + 2 x * y + 3 y^2 ] / 2
2. Constraints#
Constraints define the limitations or requirements of the optimization problem.
Keyword:
Subject To
.Structure:
Optional label (name), followed by a colon
:
.Linear expression of variables.
Optional quadratic terms enclosed in square brackets
[ ]
.Comparison operator (
=
,<=
,>=
,<
,>
).Right-hand side numerical value.
Note: Inequalities <
and <=
(or >
and >=
) are treated the same; strict inequalities are not distinguished.
Examples:
Linear Constraint:
c1: 2.5 x + 2.3 y + 5.3 z <= 8.1
Quadratic Constraint:
qc1: x + y + [ x^2 - 2 x * y + 3 y^2 ] <= 5
Indicator Constraint:
Indicator constraints enforce a constraint based on the value of a binary variable. Structure:
binary_var = value -> constraint
.ind1: b1 = 1 -> x + y <= 2
3. Bounds#
Specifies the lower and upper bounds for variables. By default, each variable has a lower bound of 0 and an infinite upper bound.
Keyword:
Bounds
.Structure:
Each line defines bounds for a variable.
Can specify lower bound, upper bound, or both.
Use
free
to indicate a variable without bounds.Use
Inf
orInfinity
for unbounded variables.
Examples:
Bounds
0 <= x <= 5
y <= 1.2
z >= 3
w free
4. Variable Types#
Defines the type of variables used in the model. By default, variables are assumed to be continuous.
Keywords:
Binary
,Binaries
,Bin
: For binary variables (0 or 1).General
,Generals
,Gen
: For general integer variables.Semi-Continuous
,Semis
,Semi
: For variables that are either zero or within a specific range.
Structure: Header keyword followed by a list of variable names.
Example:
Binary
b1 b2 b3
General
x y z
5. Special Constraints#
SOS Constraints#
Defines Special Ordered Sets (SOS) of type 1 or 2.
Keyword:
SOS
.Structure:
Name of the SOS constraint, followed by a colon
:
.Type (
S1
for SOS1,S2
for SOS2), followed by::
.List of variables with assigned weights.
Example:
SOS
sos1: S1 :: x1 : 1 x2 : 2 x3 : 3
sos2: S2 :: y1 : 1 y2 : 2 y3 : 3
Indicator Constraints#
Indicator constraints enforce a constraint based on the value of a binary variable.
Structure:
Optional label (name), followed by a colon
:
.Binary variable,
=
, value (0
or1
),->
, linear constraint.
Example:
Subject To
ind1: b1 = 1 -> x + y <= 2
Note: Indicator constraints are included in the Subject To
section.
6. End Statement#
The LP file concludes with an End
statement to indicate the end of the model.
End
Examples of LP Models#
Below are three examples of LP files representing different types of optimization problems: an LP, MIP, and MIQCQP.
Example 1: Linear Programming (LP) Problem#
\ Linear Programming Example
Minimize
obj: 3 x1 + 5 x2
Subject To
c1: 2 x1 + 3 x2 >= 12
c2: -x1 + x2 <= 3
Bounds
x1 >= 0
x2 >= 0
End
Explanation:
Objective: Minimize the cost function \(3 x_1 + 5 x_2\).
Constraints:
\(c1\): \(2 x_1 + 3 x_2 \geq 12\).
\(c2\): \(-x_1 + x_2 \leq 3\).
Bounds: \(x_1\) and \(x_2\) are non-negative.
Example 2: Mixed-Integer Programming (MIP) Problem#
\ Mixed-Integer Programming Example
Maximize
obj: 10 x1 + 6 x2 + 4 x3
Subject To
c1: x1 + x2 + x3 <= 100
c2: 10 x1 + 4 x2 + 5 x3 <= 600
c3: 2 x1 + 2 x2 + 6 x3 <= 300
Bounds
x1 >= 0
x2 >= 0
x3 >= 0
General
x1 x2 x3
End
Explanation:
Objective: Maximize profit \(10 x_1 + 6 x_2 + 4 x_3\).
Constraints:
\(c1\): Total units \(x_1 + x_2 + x_3 \leq 100\).
\(c2\): Resource constraint \(10 x_1 + 4 x_2 + 5 x_3 \leq 600\).
\(c3\): Resource constraint \(2 x_1 + 2 x_2 + 6 x_3 \leq 300\).
Bounds: All variables are non-negative.
Variable Types: \(x_1\), \(x_2\), \(x_3\) are general integers.
Example 3: Mixed-Integer Quadratically Constrained Quadratic Programming (MIQCQP) Problem#
\ MIQCQP Example
Minimize
obj: x^2 + y^2 + z^2
Subject To
c1: x + y + z >= 1
qc1: [ x^2 + y^2 ] <= 1
Bounds
x >= 0
y >= 0
z >= 0
Binary
z
End
Explanation:
Objective: Minimize the sum of squares \(x^2 + y^2 + z^2\).
Constraints:
\(c1\): Sum constraint \(x + y + z \geq 1\).
\(qc1\): Quadratic constraint \(x^2 + y^2 \leq 1\).
Bounds: All variables are non-negative.
Variable Types: \(z\) is a binary variable.
Additional Notes#
Naming Conventions#
Variable Names: Must be unique and can be up to 255 characters long.
Allowed Characters: Letters, numbers, and underscores.
Restrictions:
Cannot start with numbers or special characters like
+
,-
,*
,^
,<
,>
,=
,(
,)
,[
,]
,,
or:
.Should not contain spaces or any of the above special characters.
Avoid using reserved keywords (e.g.,
min
,max
,subject to
,bounds
,binary
,end
).
Whitespace Sensitivity#
Whitespace is used to separate tokens. For example,
x + y + z
is valid, whilex+y+z
would be interpreted as a single variable name.
Order of Sections#
It’s best to follow the conventional order for readability.
Consistency#
Ensure consistent use of variable and constraint names throughout the file.
Decimal Points#
Use periods
.
for decimal points, not commas,
.
Case Sensitivity#
The LP format is case-insensitive, but it’s good practice to be consistent.
Conclusion#
The LP format is a versatile and user-friendly way to represent optimization models. By adhering to the conventions and structures outlined above, you can effectively define various optimization problems, from simple linear programs to complex mixed-integer quadratically constrained models, in a format that is both readable and compatible with many optimization solvers.
Comments#
Lines starting with a backslash
\
are treated as comments and are ignored by the parser.