# Issues with an optimization problem

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.

I want to find the largest integer value such that it is less than $T$ and not satisfied by $Ax+By+Cz$, how can I do it without using brute force.

I can use LinearProgramming but that will give me the value that is satisfied by $Ax+By+Cz$ such that it is less than T. But I want to find the largest value which is less than T, but doesn't belong to $Ax+By+Cz$ for any value of x, y and z

• Linear programming won't help you one bit since everything is an integer. Can you solve the problem if $C = 0$? – Yuval Filmus May 13 '13 at 2:07
• @Yuval Filmus The constants A,B, C are greater than equal to 1 – user77124 May 13 '13 at 2:26
• @YuvalFilmus. I can get a suboptimal solution though when I use LP that will be approximate of the true solution. But the main thing is I don't want to have the answer that satisfied Ax+By+Cz but the one that is largest but less than T and also isn't given by Ax+By+Cz for any integer value of x,y and z – user77124 May 13 '13 at 2:28
• I suggest you first try to solve the easier $Ax+By$ case, which corresponds to $C=0$. Perhaps even start with $Ax$, i.e. $B=C=0$. That might help you solve the actual problem. – Yuval Filmus May 13 '13 at 4:22
• See this related problem on Math.SE – Peter Shor Sep 16 '13 at 20:48