Linear Programming

Linear programming (LP) is the fundamental modeling method of Operations Research. But briefly an LP should adhere to the following rules.

• Neither constraints nor the objective function may contain non-linear terms.
• Decision variables are all continuous. They may not be binary or integer.
• Decision variables can be either non-negative (\(x \ge 0\)) or unrestricted (urs).

Mathematical Model

A mathematical representation of LP model is provided below.

\[\begin{gather} \min c^\mathsf{T}x \\ Ax = b \\ x \ge 0 \\ \end{gather}\]

Parts of the Model

An LP model requires the following object types to be complete.

• Decision Variables (DV): Decision variables are the objects which the algorithm (i.e. solver) decides its value. A combination of a decision variable value set is a solution. In LP it is not possible to define a DV in non-linear (e.g., \(x^2\)) terms or in interaction with other DVs (e.g., \(xy\)). In the model, elements of \(x\) are decision variables. \(x\) is an \(n\)-sized vector.
• Coefficients and constants: It is possible to add pre-defined constants as coefficients to decision variables or by themselves. In the model, elements of \(A\), \(b\) and \(c\) are constants and coefficients. \(A\) is an \(m\) x \(n\) matrix, \(b\) is an \(m\)-sized vector and \(c\) is an \(n\)-sized vector.
• Constraints: Constraints are the rules which the decision variable values should satisfy in order to be a valid (i.e. feasible) solution. In the model, \(Ax = b\) system of equations and non-negativity terms (\(x \ge 0\)) are the constraints.
• Objective Function: Objective function defines the direction (either minimization or maximization) and the evaluation formula of the solution quality. In the model, the term \(\min c^\mathsf{T}x\) is the objective function and the solver will try to minimize \(c^\mathsf{T}x\).

Indices

There are also indices which we will use to define elements in decision variables, coefficients, constants and constraints. For instance \(x_{i}\) is the \(i\) th element of the decision variable vector and \(A_{i,j}\) is the (i,j)th element of the coefficient matrix. Let’s rewrite the model.

\[\begin{gather} \min \sum_{j=1}^{n} c_jx_j \tag{1} \\ \sum_{j=1}^{n}A_{i,j}x_j = b_i \ \forall_{i \in 1..m}\tag{2} \\ x_j \ge 0 \ \forall_{j \in 1..n} \tag{3} \\ \end{gather}\]

These parts may also be multi-dimensional. For instance \(x_{i,j,k,t}\) is possible.