.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:

  1. Objective Function

  2. Constraints

  3. Bounds

  4. Variable Types

  5. Special Constraints (SOS and Indicator)

  6. 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 like x * 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 or Infinity 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 or 1), ->, 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#

Comments#

  • Lines starting with a backslash \ are treated as comments and are ignored by the parser.

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, while x+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.