0
$\begingroup$

Given \begin{align} X+Y&\leq C_1\\ Y+Z&\leq C_2\\ Z+X&\leq C_3 \end{align}

Find the maximum of $X+Y+Z$, where $X, Y, Z$ are non-negative integers and $C_1, C_2, C_3$ are positive integers $C_1, C_2, C_3$ are given.

This is NOT a homework problem, I derived these equations from an algorithm problem.

$\endgroup$
  • $\begingroup$ Please read this How to ask good questions to get started and include your attempt in the questions for more appropriate answer . Otherwise , many users might vote to close down the question as it stand currently. $\endgroup$ – The Demonix _ Hermit Dec 11 '19 at 15:49
  • $\begingroup$ While it may not be a homework question, users on this site still do not tend to answer questions where there is no clear effort made by the asker. Please add any work you have already done so that we can help you from the point you got stuck, or list some techniques you know of that may be useful so we know what your level of knowledge is $\endgroup$ – lioness99a Dec 11 '19 at 15:55
  • 1
    $\begingroup$ Given that you're working on algorithms, have you learnt Linear Programming? $\endgroup$ – Calvin Lin Dec 11 '19 at 16:11
  • $\begingroup$ @Calvin Lin,a bit yes,not rigorously though,would be helpful if you could keep your approach a bit basic $\endgroup$ – Ajay Sabarish Dec 11 '19 at 20:03
  • $\begingroup$ @CalvinLin: it is even Integer Linear Programming. $\endgroup$ – Yves Daoust Dec 11 '19 at 20:19
3
$\begingroup$

Like JMP, we assume that WLOG $c_1\le c_2\le c_3$. Considering the first octant, the first inequation delimits a semi-infinite triangular prism with base $(0,0,0),(c_1,0,0),(0,c_1,0)$.

The second inequation truncates this prism and forms the vertices $(0,0,c_2),(c_1,0,c_2),(0,c_1,c_2-c_1)$.

Now for the third inequation we have two cases, depending on the value of $z+x$ of the vertex $(c_1,0,c_2)$, which is $c_1+c_2$. If $c_1+c_2\le c_3$, the whole prism remains and the maximum value of the sum is $c_1+c_2$ (violet dot). Otherwise, we have three new vertices, among which the intersection of the three oblique planes, $\frac12(c_1+c_2-c_3,c_2+c_1-c_3,c_2+c_3-c_1)$, that gives $\frac{c_1+c_2+c_3}2$ (red dot).

To summarize, and coming back to the general case,

  • if $c_1+c_2+c_3\le 2c_{max}\to c_1+c_2+c_3-c_{max}$,
  • else $\dfrac{c_1+c_2+c_3}2$.

enter image description here

Note that the discussion is not completely over as the given solution may involve half-integer coordinates. I cannot swear that it suffices to truncate them.


Update:

If $c_1+c_2+c_3$ is even or if $c_1+c_2+c_3\le 2c_{max}$, the previous discussion holds as all values are integer. Otherwise, all three coordinates of the optimal solution are half integers, and we can adjust them by subtracting twice $\frac12$ and adding it once. Doing so, no constraint is violated, and the sum decreases by $\frac12$, the smallest possible quantity. Hence we have three equivalent solutions giving the sum $\frac{c_1+c_2+c_3-1}2$.

Finally,

  • $c_1+c_2+c_3\le2c_{max}\to c_1+c_2+c_3-c_{max}$;

  • $c_1+c_2+c_3\ge2c_{max}\to\left\lfloor\dfrac{c_1+c_2+c_3}2\right\rfloor$.


Update:

A more elegant approach is possible with a change of coordinates. Let the LHS of the given inequalities be $u,v,w$. By inversion, we have

$$\begin{cases}2x=u-v+w,\\2y=u+v-w,\\2z=-u+v+w.\end{cases}$$

The constraints on the unknows are thus

$$\begin{cases}u\le c_1,\\v\le c_2,\\w\le c_3,\\u+w\ge v,\\u+v\ge w,\\v+w\ge u.\end{cases}$$

The last three can be combined as

$$u+v+w\ge 2u, 2v, 2w$$ or $$u+v+w\ge2\max(u,v,w).$$

Now we want to maximize $x+y+z=\dfrac{u+v+w}2$, i.e. find the plane $u+v+z=s$ that intersects the allowed volume as far as possible from the origin.

We have two cases:

  • if $c_1+c_2+c_3\ge2\max(c_1,c_2,c_3)$, that plane is by the vertex $(c_1,c_2,c_3)$ and the sum is $\dfrac{c_1+c_2+c_3}2$;

  • if $c_1+c_2+c_3\le2\max(c_1,c_2,c_3)$, the plane is $u+v+w=2\max(c_1,c_2,c_3)$ and "cuts the corner".

$\endgroup$
  • $\begingroup$ @JMP: $(c_m,0,0)$ violates one of the constraints $x\le c_1$ or $x\le c_3$. $\endgroup$ – Yves Daoust Dec 11 '19 at 19:58

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