# How to solve the coupled integer programming problem?

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)$?

• 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. – Mehdi Jafarnia Jahromi May 4 '15 at 17:29
• I do not know that. Which solver can I use? – Kira May 4 '15 at 18:01
• For example, in python you can use pulp. See this link: pypi.python.org/pypi/PuLP/1.1 – Mehdi Jafarnia Jahromi May 4 '15 at 18:05

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$$