1
$\begingroup$

I am woring on a problem and I got these inequalities.

$t_{01}+t_{11}+t_{21}\ge 4$

$t_{02}+t_{12}+t_{22}\ge 4$

$t_{10}+t_{11}+t_{12}\ge 4$

$t_{10}+t_{01}+t_{22}\ge 4$

$t_{10}+t_{02}+t_{21}\ge 4$

$t_{20}+t_{21}+t_{22}\ge 4$

$t_{20}+t_{01}+t_{12}\ge 4$

$t_{20}+t_{02}+t_{11}\ge 4$

There are $8$ integer unknowns, $t_{ij}\ge 0, 0\le i \le2, 0\le j \le2, t_{00}$ is missing. Every unknown is used in exacly 3 inequalitites. The problem is to find solution that minimizes sum of all $t_{ij}$.

If we sum all inequalities will get

$3\times \sum \ge 8\times 4$

$\sum \ge 11$

I have got this solution $t_{ij}= \begin{bmatrix} & 2 & 2 \\ 2 & 2 & 0 \\ 2 & 0 & 2 \end{bmatrix}$ and I need hint to prove that it optimal. Sum of all unknowns is $12$ here. Maybe linear programming method can be used?

$\endgroup$
3
  • $\begingroup$ This can be solved as a MIxed Integer Programming (MIP) problem. It is so small any MIP solver will do (even Solver inside Excel will suffice). $\endgroup$ Commented Jan 5, 2016 at 21:53
  • $\begingroup$ I will try a solver but anyway I hope to find an analytic solution. $\endgroup$ Commented Jan 6, 2016 at 20:07
  • $\begingroup$ I think analytic solutions are difficult. I ran with a MIP solver and got 12 as proven optimal objective. $\endgroup$ Commented Jan 6, 2016 at 23:35

1 Answer 1

Reset to default
0
$\begingroup$

Finally I found a solution.

Let one of $t_{ij}$ be $2$ (if there is $3$, using same idea we can even prove that sum is $\ge13$).

Let $t_{02}=2$.

If $t_{01}=0$ then $t_{10}+t_{22}\ge4$ and $t_{11}+t_{21}\ge4$ and $t_{12}+t_{20}\ge4$ so sum of all $t_{ij}\ge 2 + 0 + 4 + 4 + 4 = 14$

If $t_{01}=1$ then $t_{10}+t_{22}\ge3$ and $t_{11}+t_{21}\ge3$ and $t_{12}+t_{20}\ge3$ so sum of all $t_{ij}\ge 2 + 1 + 3 + 3 + 3 = 12$

If $t_{01}=2$ then $t_{10}+t_{11}+t_{12}\ge4$ and $t_{20}+t_{21}+t_{22}\ge4$ so sum of all $t_{ij}\ge 2 + 2 + 4 + 4 = 12$

So for all cases we have sum of all $t_{ij}\ge 12$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.