Linear Programming: Algorithms and Theory

Introduction

In this lecture, we transition from modeling problems using integer linear programming, as discussed in previous sessions, to exploring the algorithms and mathematical theory behind solving these models. While we have previously treated the solvers as a "black box," we now aim to delve into this "black box" to understand the underlying mechanisms for solving linear programming (LP) and integer linear programming (ILP) problems. It’s important to note that integer linear programming builds upon the foundations of linear programming. Therefore, we will first focus on understanding how to solve linear programming problems before moving on to the more complex realm of integer linear programming.

This part of the course will become more technical, involving mathematical notation and concepts that may be initially challenging. The goal is to grasp the high-level functioning of algorithms for linear programming. Detailed technical aspects can be studied later. The content from this point onwards will be more focused on mathematical notation and derivations, in contrast to the more intuitive and discursive lectures delivered previously. Efforts have been made to simplify the material where possible.

Linear Programming: Fundamentals

Definition of a Linear Program

A linear program (LP) seeks to optimize (maximize or minimize) a linear objective function subject to a set of linear constraints. These constraints are expressed as linear inequalities and/or linear equations. The solution space consists of vectors with real-valued components. An instance of a linear programming problem is referred to as a linear program.

General Formulation of a Linear Program

A linear program with \(M\) constraints and \(N\) variables in its general form is structured as follows: \[\begin{aligned} \text{Maximize } & C^T X \\ \text{Subject to } & A_i^T X \leq B_i, \quad \forall i \in I \\ & A_i^T X = B_i, \quad \forall i \in E \\ & X_j \geq 0, \quad \forall j \in C \\ & X_j \in \mathbb{R}, \quad \forall j \in U \end{aligned}\] Where:

• \(C \in \mathbb{R}^N\) is the cost vector.

• \(X \in \mathbb{R}^N\) is the vector of variables.

• \(A_i^T\) represents the \(i\)-th row of the constraint matrix \(A \in \mathbb{R}^{M \times N}\).

• \(B_i \in \mathbb{R}\) is the right-hand side constant for the \(i\)-th constraint.

• \(I\) is the index set for inequality constraints.

• \(E\) is the index set for equality constraints.

• \(C\) is the index set for variables constrained to be non-negative.

• \(U\) is the index set for unrestricted variables.

The sets \(I\) and \(E\) form a partition of the constraint set, and \(C\) and \(U\) partition the variable set.

Objective Function

The objective is to maximize or minimize a linear function, \(C^T X\), which is the dot product of the cost vector \(C\) and the variable vector \(X\).

Constraints

Constraints define the feasible region. They are linear relationships that must be satisfied by any feasible solution.

Inequality Constraints

These are given by \(A_i^T X \leq B_i\) for \(i \in I\). Any "greater than or equal to" inequality can be converted to this form by multiplying by \(-1\). Conventionally, maximization problems use "\(\leq\)" inequalities, while minimization problems use "\(\geq\)" inequalities for canonical form.

Equality Constraints

These are given by \(A_i^T X = B_i\) for \(i \in E\). While equalities are included, each equality constraint can be replaced by two inequality constraints (\(A_i^T X \leq B_i\) and \(A_i^T X \geq B_i\)). However, inequalities cannot generally be represented by equalities alone without introducing additional variables.

Variable Types

Linear programs accommodate different types of variables:

Non-negative Variables

For \(j \in C\), variables \(X_j\) are restricted to be non-negative: \(X_j \geq 0\).

Unrestricted Variables

For \(j \in U\), variables \(X_j\) are unrestricted and can take any real value, \(X_j \in \mathbb{R}\).

Matrix Representation

For a more compact representation, we can use matrix notation. Let \(A\) be the constraint matrix formed by rows \(A_i^T\). Assume the first \(M_1\) rows correspond to inequalities and the next \(M_2\) to equalities (\(M_1+M_2 = M\)). Similarly, let the first \(N_1\) variables be non-negative and the next \(N_2\) be unrestricted (\(N_1+N_2 = N\)).

Partitioning the Constraint Matrix \(A\)

Partition \(A\) into submatrices based on constraint and variable types: \[A = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}\] where \(A_{11} \in \mathbb{R}^{M_1 \times N_1}\), \(A_{12} \in \mathbb{R}^{M_1 \times N_2}\), \(A_{21} \in \mathbb{R}^{M_2 \times N_1}\), and \(A_{22} \in \mathbb{R}^{M_2 \times N_2}\).

Partitioning Vectors \(C\), \(X\), and \(B\)

Partition the vectors accordingly: \[C = \begin{pmatrix} C_1 \\ C_2 \end{pmatrix}, \quad X = \begin{pmatrix} X_1 \\ X_2 \end{pmatrix}, \quad B = \begin{pmatrix} B_1 \\ B_2 \end{pmatrix}\] where \(C_1 \in \mathbb{R}^{N_1}\), \(C_2 \in \mathbb{R}^{N_2}\), \(X_1 \in \mathbb{R}^{N_1}\), \(X_2 \in \mathbb{R}^{N_2}\), \(B_1 \in \mathbb{R}^{M_1}\), and \(B_2 \in \mathbb{R}^{M_2}\).

Matrix Form of the Linear Program

The linear program in matrix form is: \[\begin{aligned} \text{Maximize } & C_1^T X_1 + C_2^T X_2 \\ \text{Subject to } & A_{11} X_1 + A_{12} X_2 \leq B_1 \\ & A_{21} X_1 + A_{22} X_2 = B_2 \\ & X_1 \geq 0 \\ & X_2 \in \mathbb{R} \end{aligned}\] Here, \(X_1 \geq 0\) denotes that all components of \(X_1\) are non-negative, and \(A_{11} X_1 + A_{12} X_2 \leq B_1\) represents \(M_1\) inequality constraints.

Canonical Form

Definition

A linear program is in canonical form if it is a maximization problem with all constraints as "\(\leq\)" inequalities and all variables are non-negative. For minimization, the canonical form uses "\(\geq\)" inequalities and non-negative variables.

Maximization Canonical Form

\[\begin{aligned} \text{Maximize } & C^T X \\ \text{Subject to } & AX \leq B \\ & X \geq 0 \end{aligned}\] This is compactly written as: \[\text{Maximize } \{C^T X \mid AX \leq B, X \geq 0 \}\]

Minimization Canonical Form

\[\begin{aligned} \text{Minimize } & C^T X \\ \text{Subject to } & AX \geq B \\ & X \geq 0 \end{aligned}\]

Standard Form

Definition

A linear program is in standard form if it is a maximization problem with all constraints as equality constraints and all variables are non-negative.

Standard Form Representation

\[\begin{aligned} \text{Maximize } & C^T X \\ \text{Subject to } & AX = B \\ & X \geq 0 \end{aligned}\] Compactly written as: \[\text{Maximize } \{C^T X \mid AX = B, X \geq 0 \}\] Both canonical and standard forms enforce non-negativity of variables. The distinction lies in the constraint type: canonical form uses inequalities, and standard form uses equalities.

Transformations and Equivalences in Linear Programming

Equivalence of Different LP Forms

Linear programs can be expressed in various forms (general, canonical, standard), yet these forms are fundamentally equivalent. Transforming a linear program from one form to another does not alter the underlying problem; solving a transformed problem in canonical or standard form yields a solution that can be mapped back to the original problem. This equivalence is crucial because certain algorithms are designed to operate on specific forms, such as the standard form.

Converting Inequality Constraints to Equality Constraints

To facilitate the use of algorithms designed for equality constraints, we can convert inequality constraints into equalities by introducing slack or surplus variables.

Introducing Slack Variables (for \(\leq\) inequalities)

For a "less than or equal to" inequality constraint, \(A_i^T X \leq B_i\), we introduce a non-negative slack variable, \(S_i \geq 0\), to convert it into an equality: \[A_i^T X + S_i = B_i, \quad S_i \geq 0 \label{eq:slack_variable}\] The slack variable \(S_i\) represents the slack or unused resource on the left-hand side of the inequality compared to the limit \(B_i\). The inequality \(A_i^T X \leq B_i\) holds if and only if there exists a non-negative \(S_i\) such that equation [eq:slack_variable] is satisfied.

Introducing Surplus Variables (for \(\geq\) inequalities)

For a "greater than or equal to" inequality constraint, \(A_i^T X \geq B_i\), we introduce a non-negative surplus variable, \(E_i \geq 0\), to convert it into an equality: \[A_i^T X - E_i = B_i, \quad E_i \geq 0 \label{eq:surplus_variable}\] The surplus variable \(E_i\) represents the surplus or excess of the left-hand side of the inequality over the requirement \(B_i\). The inequality \(A_i^T X \geq B_i\) holds if and only if there exists a non-negative \(E_i\) satisfying equation [eq:surplus_variable].

Handling Unrestricted Variables

Substitution with Non-negative Variables

If a variable \(X_j\) is unrestricted in sign, it can be expressed as the difference of two non-negative variables, \(X_j^+\) and \(X_j^-\), where \(X_j^+ \geq 0\) and \(X_j^- \geq 0\). We substitute \(X_j\) as: \[X_j = X_j^+ - X_j^-, \quad X_j^+ \geq 0, X_j^- \geq 0 \label{eq:unrestricted_variable}\] This substitution is valid because any real number can be represented as the difference of two non-negative numbers. For instance, \(5 = 5 - 0\) and \(-5 = 0 - 5\). By applying this substitution to each unrestricted variable, we can transform any linear program to one with only non-negative variables.

Converting Between Maximization and Minimization Problems

Conversion between maximization and minimization problems is straightforward. Maximizing an objective function \(C^T X\) is equivalent to minimizing its negative, \(-C^T X\), and vice versa. \[\text{Maximize } C^T X \equiv \text{Minimize } -C^T X\] This allows us to convert any minimization problem into a maximization problem, which is often the standard form assumed by many LP algorithms.

Illustrative Example: Transforming a General LP to Standard Form

Consider the following linear program in general form, which we aim to convert to standard form:

Initial Linear Program in General Form

\[\begin{aligned} \text{Maximize } & 3x_1 - x_2 + x_4 \\ \text{Subject to } & x_1 + 2x_2 - x_3 \leq 5 \\ & -2x_1 + x_2 - 3x_3 - x_4 = 0 \\ & x_1 + 2x_3 + 2x_4 \leq 3 \\ & x_1 \geq 0, x_3 \geq 0 \\ & x_2, x_4 \in \mathbb{R} \text{ (unrestricted)} \end{aligned}\] Note that \(x_3\) has a zero coefficient in the objective function.

Step-by-Step Transformation Process

To transform this LP into standard form, we follow these steps:

1. Replace the unrestricted variables \(x_2\) and \(x_4\) using the substitution described in [eq:unrestricted_variable].

2. Convert the inequality constraints into equality constraints by introducing slack variables as described in [eq:slack_variable].

Replacing Unrestricted Variables

Let \(x_2 = x_2^+ - x_5\) and \(x_4 = x_4^+ - x_6\), where \(x_2^+, x_5, x_4^+, x_6 \geq 0\). For notational simplicity, and consistent with the lecture, we will drop the \(+\) superscript and use \(x_2\) and \(x_4\) to represent the non-negative variables \(x_2^+\) and \(x_4^+\) respectively. Thus, we set \(x_2 = x_2 - x_5\) and \(x_4 = x_4 - x_6\), with \(x_2, x_5, x_4, x_6 \geq 0\). It is important to recognize that the newly introduced \(x_2\) and \(x_4\) are distinct non-negative variables, replacing the original unrestricted variables, even though we reuse the symbols for simplicity.

Introducing Slack Variables

Introduce slack variables \(x_7 \geq 0\) for the first inequality and \(x_8 \geq 0\) for the third inequality to convert them to equalities: \[\begin{aligned} x_1 + 2x_2 - x_3 - 2x_5 + x_7 &= 5 \\ x_1 + 2x_3 + 2x_4 - 2x_6 + x_8 &= 3 \end{aligned}\]

Resulting Linear Program in Standard Form

Substituting for unrestricted variables and adding slack variables, the LP in standard form becomes: \[\begin{aligned} \text{Maximize } & 3x_1 - (x_2 - x_5) + (x_4 - x_6) \\ \text{Subject to } & x_1 + 2(x_2 - x_5) - x_3 + x_7 = 5 \\ & -2x_1 + (x_2 - x_5) - 3x_3 - (x_4 - x_6) = 0 \\ & x_1 + 2x_3 + 2(x_4 - x_6) + x_8 = 3 \\ & x_1 \geq 0, x_3 \geq 0, x_2 \geq 0, x_5 \geq 0, x_4 \geq 0, x_6 \geq 0, x_7 \geq 0, x_8 \geq 0 \end{aligned}\] Simplifying the objective function and constraints, we obtain the standard form: \[\begin{aligned} \text{Maximize } & 3x_1 - x_2 + x_4 + x_5 - x_6 \\ \text{Subject to } & x_1 + 2x_2 - x_3 - 2x_5 + x_7 = 5 \\ & -2x_1 + x_2 - 3x_3 - x_4 - x_5 + x_6 = 0 \\ & x_1 + 2x_3 + 2x_4 - 2x_6 + x_8 = 3 \\ & x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8 \geq 0 \end{aligned}\] This linear program is now in standard form, featuring only equality constraints and non-negative variables.

Equivalence of Solutions

The standard form LP is equivalent to the original general form LP. Given an optimal solution \((x_1^*, x_2^*, x_3^*, x_4^*, x_5^*, x_6^*, x_7^*, x_8^*)\) for the standard form problem, the optimal solution for the original problem is recovered by setting the original variables as \((x_1^*, x_2^* - x_5^*, x_3^*, x_4^* - x_6^*)\). The slack variables \(x_7^*\) and \(x_8^*\) are auxiliary variables introduced for transformation and do not directly correspond to variables in the original problem. They ensure that the inequality constraints of the original problem are satisfied.

Conclusion

In this lecture, we have established the foundational concepts for solving linear programming problems. We defined linear programs, explored their general formulation, matrix representation, canonical form, and standard form. Crucially, we examined the transformations that enable the conversion of any linear program into an equivalent problem in standard or canonical form. These transformations include the introduction of slack and surplus variables to convert inequality constraints into equality constraints, and the substitution of unrestricted variables with the difference of non-negative variables. These transformations are not merely theoretical manipulations; they are essential because many fundamental algorithms for solving linear programs, such as the simplex method, are designed to operate on problems in standard form. Therefore, mastering these transformation techniques is vital for applying these algorithms effectively to any linear programming problem, irrespective of its initial formulation.

Building upon this foundation, subsequent lectures will delve into the algorithms themselves, utilizing these standardized forms to develop efficient methods for finding optimal solutions to linear programming problems.