# Canonical form of a linear program

I have a linear programming problem that I want to write in the canonical form: \begin{align}\min&\quad c^\top X\\\text{s.t.}&\quad A\cdot X\le b\end{align}

The problem is given by \begin{align}\min&\quad m^\top X\\\text{s.t.}&\quad max\left(\frac{\sum_{i=1}^{\tau}(L_{i}-S_{i})\cdot D_{i}}{D_{\tau} }\right ) \leq \alpha,\quad \forall\tau\in\{1,2,\dots,t\}\tag1\end{align} (A numerical example is given at the bottom)

Another range constraint is given by $${\rm lb} \leq Q^\top X \leq{\rm ub}\tag2$$ where

• $$m$$ is an $$n\times1$$ matrix

• $$P$$ is an $$n\times t$$ matrix

• $$L$$ is $$t\times1$$ matrix

• $$Q$$ is $$n\times1$$ matrix

• $$D$$ is $$t\times1$$ matrix

• $$X$$ is $$n\times1$$ matrix of decision variables

• $$S= P^\top X$$ is $$t\times1$$ matrix

Bounds on the decision variable $$X$$ are given by: $$l \leq x \leq u$$

The range constraint can be rewritten as one constraint by introducing a variable y:

$$y+ Q^{T}X = {\rm ub} – {\rm lb}$$
where $$0 \leq y \leq {\rm ub} - {\rm lb}$$

Here is a numerical example to explain the constraint (1)

$$X = \begin{pmatrix} x_{1} \\\ x_{2}\\\ x_{3} \\ \end{pmatrix}$$ , $$P = \begin{pmatrix} 10 & 10 & 20 & 30 \\ 200 & 30 & 50 & 150\\ 7 & 100 & 99 & 1000 \end{pmatrix}$$ , $$m = \begin{pmatrix} 20 \\ 200\\ 700 \end{pmatrix}$$ , $$D = \begin{pmatrix} 1.5 \\ 0.05\\ 0.9\\ 0.15 \end{pmatrix}$$ ,$$Q = \begin{pmatrix} 45 \\\ 55\\\ 1000\\ \end{pmatrix}$$ ,$$L = \begin{pmatrix} 20 \\\ 33\\\ 53\\\ 990 \end{pmatrix}$$ ,$$S = P^{T}X$$ = $$\begin{pmatrix} 10x_{1}+200x_{2}+7x_{3} \\\ 10x_{1}+30x_{2}+100x_{3}\\\ 20x_{1}+50x_{2}+99x_{3} \\\ 30x_{1}+150x_{2}+1000x_{3} \end{pmatrix}$$

Linearizing constraint (1) leads to a set of 4 constraints in this example. Constraint (1) is given by: $$t =1, \frac{(20-\begin{pmatrix} 10x_{1}+200x_{2}+7x_{3} \\\end{pmatrix}) *1.5}{1.5} \leq \alpha$$

$$t =2, \frac{(33-\begin{pmatrix} 10x_{1}+30x_{2}+100x_{3} \\\end{pmatrix})*0.05+(20-\begin{pmatrix} 10x_{1}+200x_{2}+7x_{3} \\\end{pmatrix}) *1.5}{0.05} \leq \alpha$$

$$t =3, \frac{(53-\begin{pmatrix} 20x_{1}+50x_{2}+99x_{3} \\\end{pmatrix})*0.9+(33-\begin{pmatrix} 10x_{1}+30x_{2}+100x_{3} \\\end{pmatrix})*0.05+(20-\begin{pmatrix} 10x_{1}+200x_{2}+7x_{3} \\\end{pmatrix}) *1.5}{0.9} \leq \alpha$$

$$t =4, \frac{(990-\begin{pmatrix} 30x_{1}+150x_{2}+1000x_{3} \\\end{pmatrix})*0.15+(53-\begin{pmatrix} 20x_{1}+50x_{2}+99x_{3} \\\end{pmatrix})*0.9+(33-\begin{pmatrix} 10x_{1}+30x_{2}+100x_{3} \\\end{pmatrix})*0.05+(20-\begin{pmatrix} 10x_{1}+200x_{2}+7x_{3} \\\end{pmatrix}) *1.5}{0.15} \leq \alpha$$

$$Constraint\ (2)\ is\ given\ by:y+Q^{T}X = ub – lb$$

$$y+\begin{pmatrix} 45x_{1}+55x_{2}+1000x_{3} \\\end{pmatrix} =ub - lb$$

where $$0 \leq y \leq ub-lb$$

Constraint (1) can be written as: $$\sum_{i=1}^{\tau}(L_{i}\cdot D_{i}-P^{T}\cdot D_{i}\cdot X) \leq \alpha\cdot{D_{\tau}}$$ $$\sum_{i=1}^{\tau}(-P^{T}\cdot D_{i}) X = \alpha\cdot D_{\tau}-\sum_{i=1}^{\tau}L_{i}\cdot D_{i}\space\ \forall\tau\in\left \{ 1,2,...t \right \}$$

where LHS will form part of the matrix A and

RHS will form part of the matrix b in the canonical form.

In the example, the part of the matrix A corresponding to constraint (1) can be determined by calculating cumulative sum of rows of $$P^{T}\cdot D_{i}$$

$$A_{con1}=\sum_{i=1}^{\tau}P^{T}\cdot D_{i}\hspace{0.5cm} \forall\tau\in\{1,2,\dots,4\} =\begin{pmatrix} 15 & 300 & 10.5 \\ 15.5 & 301.5 & 15.5 \\ 33.5 & 346.5 & 104.6 \\ 38& 369 & 254.6\end{pmatrix}$$

Assuming $$\alpha=2$$, the part of the matrix b for constraint (1) can be determined a: $$b_{con1}=\begin{pmatrix} 33.0 \\ 31.75\\ 81.149999\\ 228.15 \end{pmatrix}$$

Constraint (2) can be easily written in the canonical form by splitting it in two constraints $$Q^\top X \leq{\rm ub}\tag2$$ $$-Q^\top X \leq{\rm -lb}$$ But, if we reformulate it as one equality constraint by introducing a variable $$y$$ then it remains unclear on how to write it in the canonical form.

How can this problem be written in the canonical form? Bounds on variables ($$x$$ and $$y$$ in this case) are often not defined as separate constraints in AMLs. Do I need to define the bounds on variables as constraints in order to convert it in to the canonical form?

• The only thing you have identified as a variable is $X$, which means (1) involves parameters/constants only. – prubin Jul 26 at 19:57
• (1) involves X as S is generated by multiplying P and X. For brevity reasons, matrix S is defined. All other elements are constants – Simply op Jul 26 at 20:16
• I suspect your constraint (1) is written incorrectly. Is $\frac{\sum_{i=1}^\tau (L_i-S_i) D_i}{D_\tau} \leq \alpha \quad \forall \tau\in\{1,\ldots,t\}$ what you meant? – kurtosis Jul 27 at 4:43
• @kurtosis I may have written constraint (1) incorrectly. The example at the bottom of the question explains what is meant by this constraint. Constraint (1) is a max constraint which is linearized so it leads to a set of t constraints. If my example makes sense and if the correct way to writing it mathematically is the way you have described then I suggest editing the question. – Simply op Jul 27 at 9:06