🌟 Linear Programming (LP) Basics

🌟 Linear Programming (LP) Basics#

Linear Programming (LP) is a powerful mathematical method used to determine the best possible outcome—such as maximum profit or minimum cost—under a given set of linear constraints. It is widely applied in areas like operations research, economics, engineering, and logistics.

What Is an LP Optimization Model?#

A Linear Programming problem typically involves:

  • A linear objective function to be maximized or minimized

  • A set of linear constraints, which can be equalities or inequalities

  • Decision variables that represent the quantities to be determined

General Form of an LP Problem#

Objective Function:#

\[\text{maximize or minimize } f(x) = b_1x_1 + b_2x_2 + ... + b_nx_n\]

Subject to Constraints:#

\[ Kx \leq a \]

Where:

  • ( f(x) ): Objective function (the quantity to be optimized)

  • ( x = [x_1, x_2, \ldots, x_n]^T ): Vector of decision variables

  • ( b = [b_1, b_2, \ldots, b_n] ): Coefficient vector for the objective function

  • ( K ): Matrix of constraint coefficients

  • ( a ): Vector of constraint bounds

Additional conditions may include:

\[ x \geq 0 \quad \text{(non-negativity constraints)} \]

Key Concepts#

  • Feasible Region: The set of all points ( x ) that satisfy the constraints.

  • Optimal Solution: A point in the feasible region that yields the best value (maximum or minimum) for the objective function.

  • Binding Constraints: Constraints that are active at the optimal solution (they “hold tight”).

Using Gurobi for Linear Programming#

Gurobi [1] is a powerful optimization solver widely used for solving optimization problems. The Gurobipy [2] Python library provides a user-friendly interface to define and solve optimization models. The Gurobipy package includes a trial license, which allows users to solve problems of limited size [2]. However, students and faculty affiliated with academic institutions are eligible for a free, full-featured license [2].

Installing Gurobi#

If you haven’t installed Gurobipy yet, use:

pip install gurobipy

Implementing a Linear Program with Gurobi#

Problem Definition:#

Consider a simple LP problem:

Linear Programming Problem#

Maximize:

\[f = 2x + 3y\]

Subject to:

\[3x + 2y \leq 11\]
\[x + y \leq 4\]
\[x \geq 0, \quad y \geq 0\]

We will solve this problem using Gurobi in Python.

First, you need to import the entire gurobipy library and import the GRB constants from gurobipy.

import gurobipy as grb
from gurobipy import GRB

Then, you need to create a new optimization model instance, define the decision variables, and set up the objective function.

# Create a new optimization model
model = grb.Model("LP")
# Define decision variables
x = model.addVar(name="x", vtype=GRB.CONTINUOUS, lb=0)
y = model.addVar(name="y", vtype=GRB.CONTINUOUS, lb=0)
# Set objective function
model.setObjective(2*x + 3*y, GRB.MAXIMIZE)

Set parameter Username
Academic license - for non-commercial use only - expires 2026-02-10

Next, you can define the constraints:

# Add constraints
model.addConstr(3*x + 2*y <= 11, "Constraint 1")
model.addConstr(x + y <= 4, "Constraint 2")

<gurobi.Constr *Awaiting Model Update*>

Now, you can invoke Gurobi to solve this optimization problem:

# Optimize the model
model.optimize()

Gurobi Optimizer version 12.0.1 build v12.0.1rc0 (win64 - Windows 11.0 (26100.2))

CPU model: 12th Gen Intel(R) Core(TM) i5-12500H, instruction set [SSE2|AVX|AVX2]
Thread count: 12 physical cores, 16 logical processors, using up to 16 threads

Optimize a model with 2 rows, 2 columns and 4 nonzeros
Model fingerprint: 0x9496ece8
Coefficient statistics:
  Matrix range     [1e+00, 3e+00]
  Objective range  [2e+00, 3e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [4e+00, 1e+01]
Presolve time: 0.01s
Presolved: 2 rows, 2 columns, 4 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    5.0000000e+30   3.250000e+30   5.000000e+00      0s
       1    1.2000000e+01   0.000000e+00   0.000000e+00      0s

Solved in 1 iterations and 0.01 seconds (0.00 work units)
Optimal objective  1.200000000e+01

# Display results
if model.status == GRB.OPTIMAL:
    print(f"Optimal solution: x = {x.x}, y = {y.x}")
    print(f"Optimal objective value: Z = {model.objVal}")
else:
    print("No optimal solution found.")

Optimal solution: x = 0.0, y = 4.0
Optimal objective value: Z = 12.0

After running the above script, Gurobi will output the optimal values of \(x\) and \(y\), along with the optimal objective function value.

Conclusion#

Linear Programming is a mathematical optimization technique used to find the best outcome in a given system. Gurobi is a powerful solver that can efficiently handle optimization problems. This section serves as a foundation for more advanced optimization problems, including real-world applications such as grid optimization.

References#

[1] Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” 2024.

[2] Gurobi Optimization, LLC, “GurobiPy: Python interface for the Gurobi Optimizer,” PyPI, [Online]. Available: https://pypi.org/project/gurobipy/

[3] Winston, W. L. Operations Research: Applications and Algorithms. 4th ed., Duxbury Press, 2004.

Contents