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
    Commented Jul 26, 2020 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$
    – Jonn
    Commented Jul 26, 2020 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
    Commented Jul 27, 2020 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$
    – Jonn
    Commented Jul 27, 2020 at 9:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.