2 Multi‐parametric Linear Programming

Consider the following linear programming (LP) problem:

(2.1)

where , , , , , is a compact polytope and is assumed to have full rank.1 This problem formulation requires the deterministic knowledge of all elements of problem (2.1). However, in many applications values such as prices, demand, and risk might change over time and have great impact on the solution. In order to take this into account, the uncertainty can be considered explicitly by formulating a multi‐parametric linear programming (mp‐LP) problem:

(2.2)

where , , , and is a compact polytope. The difference between problems (2.1) and (2.2) is the presence of the bounded uncertain parameters in the constraints. As a result, the solution , the Lagrange multipliers and , and the optimal objective function of problem (2.2) are obtained as a function of , i.e. , , , and , respectively. A schematic representation of the difference between problem (2.1) and (2.2) is shown in Figure 2.1.

Figure 2.2 shows some of the properties of the solution of the mpLP problem 2.2.

      Remark 2.1

      Note that it is possible to add a scalar to the objective function of an LP problem without influencing the optimal solution. Similarly, it is possible to add an arbitrary scaling function to an mp‐LP problem without influencing the optimal solution.

Figure 2.1 The difference between the solution of an LP and an mp‐LP problem (black dot and line, respectively), where the mp‐LP problem is obtained by treating as a parameter. In (a), the solution is a single point in one of the vertices of the feasible space, while in (b) the solution is a function of the parameter .

2.1 Solution Properties

      Remark 2.2

Due to the similarities between mp‐LP and multi‐parametric quadratic programming (mp-QP) problems, the different solution strategies available are discussed in detail in Chapter 4.