Linear Programming — SepalSolver

The Linear Programming (LP) method approaches optimization problems where both the objective function and all constraints are linear functions of the decision variables.

LP seeks to maximize or minimize a linear objective function subject to linear inequality constraints, equality constraints, and variable bounds—guaranteeing that any local optimum is also a global optimum due to the convexity of the feasible region.

Fundamental Components of a Linear Program:

The 3-Step Formulation Process Consider a standard linear program solved via the Linprog interface:

\min_{\mathbf{x}} \quad \mathbf{f}^T \mathbf{x}

Decision Variables: Define the vector of unknown variables $\mathbf{x} = [x_1, x_2]^T$ to be optimized.

Objective Function Vector: Specify the objective coefficient vector :math:\mathbf{f}, defining the linear cost or performance surface to minimize:

f(\mathbf{x}) = f_1 x_1 + f_2 x_2 = \mathbf{f}^T \mathbf{x}

Constraints & Bounding Domains: Formulate inequality systems $\mathbf{A}\mathbf{x} \le \mathbf{b}$ , equality restrictions $\mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}$ , and lower/upper variable bounds :math:\mathbf{Lb} \le \mathbf{x} \le \mathbf{Ub}.

## Constraint Types in Linprog

The Linprog solver handles three levels of constraint complexity depending on problem parameters: - Inequality Constraints ( $\mathbf{A}\mathbf{x} \le \mathbf{b}$ ): Defines the primary polyhedral boundary of the feasible region. - Equality Constraints ( $\mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}$ ): Restricts the feasible solution domain to a lower-dimensional affine subspace or hyperplane within the polyhedron. - Variable Bounds ( $\mathbf{Lb} \le \mathbf{x} \le \mathbf{Ub}$ ): Sets direct lower and upper box constraints on individual decision variables, improving solver efficiency.

Comparison: Linprog Formulation Levels Feature | Basic Inequality LP | LP with Equality Constraints | Fully Bounded LP Objective | $\min \mathbf{f}^T \mathbf{x}$ | $\min \mathbf{f}^T \mathbf{x}$ | $\min \mathbf{f}^T \mathbf{x}$ Inequalities | $\mathbf{A}\mathbf{x} \le \mathbf{b}$ | $\mathbf{A}\mathbf{x} \le \mathbf{b}$ | $\mathbf{A}\mathbf{x} \le \mathbf{b}$ Equalities | None | $\mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}$ | $\mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}$ Variable Bounds | Implicit / Unbounded | Implicit / Unbounded | Explicit (:math:\mathbf{Lb}, \mathbf{Ub})

Example 1: Standard Linear Program with Inequality Constraints

Minimizing a linear objective function subject to a system of linear inequalities defining a 2D polyhedral feasible region:

\min \quad -x_1 - 0.3333 x_2 \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \le \mathbf{b}

Example 1C#

// SOLVE_LP_SIMPLEX Solves 2D Linear Program using standard Linear Programming solver
double[,] A = new double[,]{
    { 1.00,  1.00 },
    { 1.00,  0.25 },
    { 1.00, -1.00 },
    {-0.25, -1.00 },
    {-1.00, -1.00 },
    {-1.00,  1.00 }
};
double[] b = [2, 1, 2, 1, -1, 2];
double[] f = [-1, -1.0 / 3];
var result = Linprog(f, A, b);
Console.WriteLine(result);

OutputFrom the book

Optimal solution found

   0.6667
   1.3333

Example 2: Linear Program with Inequality and Equality Constraints

Incorporating linear equality constraints $\mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}$ to restrict the search space along a hyper-plane intersecting the feasible region:

\min \quad \mathbf{f}^T \mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \le \mathbf{b}, \quad x_1 + \frac{1}{4} x_2 = \frac{1}{2}

Example 2C#

double[,] A = new double[,]{
    { 1.00,  1.00 },
    { 1.00,  0.25 },
    { 1.00, -1.00 },
    {-0.25, -1.00 },
    {-1.00, -1.00 },
    {-1.00,  1.00 }
};
double[] b = [2, 1, 2, 1, -1, 2];
double[] f = [-1, -1.0 / 3];
double[,] Aeq = new double[,] { { 1, 1.0 / 4 } };
double[] beq = [1.0 / 2];
var result = Linprog(f, A, b, Aeq, beq);
Console.WriteLine(result);

OutputFrom the book

Optimal solution found

 0 
 2

Example 3: Fully Constrained Linear Program with Variable Bounds

Enforcing explicit lower ( $\mathbf{Lb}$ ) and upper ( $\mathbf{Ub}$ ) limits on each decision variable alongside inequality and equality systems:

\min \quad \mathbf{f}^T \mathbf{x} \quad \text{s.t.} \quad \mathbf{A}\mathbf{x} \le \mathbf{b}, \quad \mathbf{A}{eq}\mathbf{x} = \mathbf{b}{eq}, \quad \mathbf{Lb} \le \mathbf{x} \le \mathbf{Ub}

Example 3C#

double[,] A = new double[,]{
    { 1.00,  1.00 },
    { 1.00,  0.25 },
    { 1.00, -1.00 },
    {-0.25, -1.00 },
    {-1.00, -1.00 },
    {-1.00,  1.00 }
};
double[] b = [2, 1, 2, 1, -1, 2];
double[] f = [-1, -1.0/3];
double[,] Aeq = new double[,] { { 1, 1.0 / 4 } };
double[] beq = [1.0 / 2];
double[] Lb = [-1, -0.5], Ub = [1.5, 1.25];
var result = Linprog(f, A, b, Aeq, beq, Lb, Ub);
Console.WriteLine(result);

OutputFrom the book

Optimal solution found

   0.1875
   1.2500