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?

  • $\begingroup$ The only thing you have identified as a variable is $X$, which means (1) involves parameters/constants only. $\endgroup$ – prubin Jul 26 at 19:57
  • $\begingroup$ (1) involves X as S is generated by multiplying P and X. For brevity reasons, matrix S is defined. All other elements are constants $\endgroup$ – Simply op Jul 26 at 20:16
  • $\begingroup$ 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? $\endgroup$ – kurtosis Jul 27 at 4:43
  • $\begingroup$ @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. $\endgroup$ – Simply op Jul 27 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.