1
$\begingroup$

The problem may be formulated as follows:

We are given a set of $m$ positive numbers $\{b_1,...,b_m\}$ and a set of $n$ positive numbers $\{v_1,...,v_n\}$. We have $v_j\leq K$, $j=1,...,n$, for a given positive integer $K$.

We have to find a vector $x$ of size $n$ and a matrix $A$ of size ($m\times n$) such that $\textbf{1}^Tx$ is minimized and $Ax\geq b$ (componentwise). Moreover, each entry must belong to the set $\{0,1,...,K\}$ and each column $j$ of $A$ must sum to $v_j$.

Here is an example with $m=6$, $n=3$ and $K=4$. We have $b=\{2800,1600,1050,750,520,240\}$ and $v=\{1,4,3\}$. The problem is: $$\min_{a_{ij},x_j} x_1+x_2+x_3$$ $$\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\a_{41}&a_{42}&a_{43}\\a_{51}&a_{52}&a_{53}\\a_{61}&a_{62}&a_{63} \end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}\geq \begin{pmatrix}2800\\1600\\1050\\750\\520\\240\end{pmatrix},$$ $$\sum_{i=1}^6a_{i1}=1, \hspace{0.6cm}\sum_{i=1}^6a_{i2}=4, \hspace{0.6cm}\sum_{i=1}^6a_{i3}=3,$$ $$a_{ij}\in\{0,1,2,3,4\}.$$ A feasible solution would be:

$$\begin{pmatrix}1&0&0\\0&2&0\\0&0&1\\0&1&1\\0&1&0\\0&0&1 \end{pmatrix}\begin{pmatrix}2800\\800\\1050\end{pmatrix}\geq \begin{pmatrix}2800\\1600\\1050\\750\\520\\240\end{pmatrix},$$ in this case, we have $\textbf{1}^Tx=2800+800+1050=4650$. Actually, I do not know the optimal solution (the optimal pair $A$, $x$) such that $\textbf{1}^Tx$ is minimized, and I am not looking for it.

What I am looking for is a lower bound on the optimal value. A trivial idea is to solve the following LP: $$\min\{\textbf{1}^Tx \text{ s.t. } v^Tx\geq \sum_i b_i \text{ and }x\geq0\}$$

Indeed, we know the sum of each column $j$ of $A$ (it is $v_j$), hence by making the sum of all the inequalities we obtain $v^Tx\geq \sum_i b_i$. In the previous example, it gives $x_1=0$, $x_2=1740$ and $x_3=0$. Then a lower bound on the optimal value is $1740$.

But is there a way to obtain a better lower bound? For example, the previous one does not take into account that there are $m$ inequalities.

Thank you very much.

Improve this question
$\endgroup$
3
  • $\begingroup$ Why not just implement each of the $m$ inequalities $Ax \geq b$ in the LP, rather than summing them? The only part of your optimization problem that can't be formulated in the LP is the fact that the entries of $x$ must be integers. Using this relaxation shows that your given problem indeed has an optimal value of $4650$ (a fact that is obvious from the fact that one of the constraints is $x_1 \geq 2800$, one is $2x_2 \geq 1600$, and one is $x_3 \geq 1050$).. $\endgroup$
    – Nathaniel Johnston
    Commented Nov 5, 2015 at 22:29
  • $\begingroup$ @NathanielJohnston Actually, $A$ is not known. I have edited my question, I hope it is clearer now! $\endgroup$
    – user2370336
    Commented Nov 5, 2015 at 22:38
  • $\begingroup$ After your edit (i.e. with unknown $A$) it looks like a quadratic programming problem (for the unknowns $A$ and $x$). Depending on the size, if could well be solvable, even with integer constraints for the entries of $A$. You could try SCIP: scip.zib.de. $\endgroup$
    – Dirk
    Commented Nov 6, 2015 at 8:30

0

Reset to default

You must log in to answer this question.