1
$\begingroup$

I have the following integer linear programming problem:

$$\begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} && \sum_{k=1}^K\sum_{t=1}^Tx_{kt} \\ & \text{subject to} && \sum_{k=1}^Kx_{kt} \leqslant N, \; \forall t\\ &&& x_{kt}\cdot \alpha_k(t) \leqslant E_k(t), \; \forall k, t\\ &&& E_k(t+1) = E_k(t) - x_{kt}\cdot\alpha_k(t)+H_k(t), \; \forall k, t\\ &&& x_{kt}\in\{0, 1\}. \end{aligned} \end{equation*}$$

I cannot figure out how to solve it. I mean I cannot write it in a solver as :

\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f_0(x) \\ & \text{subject to} & & Ax\leqslant b. \end{aligned} \end{equation*} because of the dependencies between the inputs. $H_k(t)$ is a random variable that follows Bernoulli distribution which is given as input. $K, T, \alpha_k(t)$ are also given as input. I cannot give $E_k(t)$ as an input because of the last constraint.

How can I write it in a solver as a linear integer programming problem when $E_k(t)$ depends on the variables $x_{kt}$ and on the random variable $H_k(t)$?

$\endgroup$
  • $\begingroup$ It is not needed for you to convert it to the standard form. Most solvers can do it automatically. You just need to define the objective function and add constraints. $\endgroup$ – Mehdi Jafarnia Jahromi May 4 '15 at 17:29
  • $\begingroup$ I do not know that. Which solver can I use? $\endgroup$ – Kira May 4 '15 at 18:01
  • $\begingroup$ For example, in python you can use pulp. See this link: pypi.python.org/pypi/PuLP/1.1 $\endgroup$ – Mehdi Jafarnia Jahromi May 4 '15 at 18:05
1
$\begingroup$

Notice that you can write the sequence $\{x_{kt}\}_{K\geq k\geq1,T\geq t\geq 1} $ at a vector as so: $$x := \begin{bmatrix} x_{11} \\ x_{21} \\ \vdots \\ x_{K1} \\ x_{12} \\ \vdots \\ x_{K2} \\ \vdots \\ \vdots \\ x_{KT} \end{bmatrix}$$ Next, we can rewrite the last constraint recursively as $$ E_k(t)=E_k(0)-tx_{kt}\alpha_k(t)+tH_k(t).$$ With this, we can rewrite the second constraint as $$ (t+1)\alpha_k(t)x_{kt}\leq E_k(0)+tH_k(t)\qquad \forall k,t$$ Now to rewrite all constraints into one matrix $A$ such that $Ax\leq b$ we set $$ A=\begin{bmatrix} 1 & \dots & 1 & 0 & \dots & 0 & 0 & \dots & 0 \\ 0 & \dots & 0 & 1 & \dots & 1 & 0 & \dots & 0 \\ \vdots & \dots & \vdots & & \ddots & & \ddots \\ 0 & \dots & 0 & \dots & 0 & \dots & 1 &\dots & 1\\ 2\alpha_1(1) & 0 & \dots & \dots & \dots & \dots& \dots & \dots & 0 \\ 0 & 2\alpha_2(1) & 0 & \dots & \dots & \dots& \dots & \dots& 0\\ 0 & 0 & \ddots & 0 & \dots & \dots& \dots & \dots & 0 \\ 0 & \dots & 0 & 2\alpha_K(1) &0& \dots& \dots & \dots & 0 \\ 0 & \dots & 0 & 0 & 3\alpha_1(2)& 0& \dots & \dots & 0 \\ 0 & \dots & 0 & 0 & 0 & \ddots& 0 & \dots & 0 \\ 0 & \dots & 0 & 0 & 0 & 0 & \ddots & \dots & 0 \\ 0 & \dots & 0 & 0 & 0 & 0 & \dots & & (T+1)\alpha_K(T) \\ \end{bmatrix} $$ with the vector $$b := \begin{bmatrix} N\\ \vdots\\ N\\ E_1(0)+ H_1(1)\\ \vdots\\ E_K(0)+ H_K(1)\\ E_1(0)+ H_1(2) \\ \vdots \\ E_K(0)+ H_K(2) \\ \vdots\\\vdots\\ E_K(0)+ H_K(T) \end{bmatrix}$$

With this the problem can be written as $$ \max_{x \text{ binary vector}} \|x\|_1 \\ \text{subject to } Ax\leq b$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.