1
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ Are A, B, C, T integers? $\endgroup$ – Karolis Juodelė May 10 '13 at 17:22
  • $\begingroup$ @KarolisJuodelė Yes, they are $\endgroup$ – user77124 May 10 '13 at 17:24
  • $\begingroup$ Somewhere in the editing of the question the requirement $Ax+By+Cz\le T$ has been lost! $\endgroup$ – Hendrik Jan May 11 '13 at 11:22
  • $\begingroup$ In the current version I cant tell what is asked. What does it mean that an integer satisfies $Ax+By+Cz$? $\endgroup$ – A.Schulz May 13 '13 at 7:12
  • $\begingroup$ @A.Schulz. Integer satisfies $Ax+By+Cz$. It means lets say we have an integer M. Then M can be obtained from $Ax+By+Cz$ by using integer values of x,y and z and getting exactly value M $\endgroup$ – user77124 May 13 '13 at 20:00
3
$\begingroup$

This is classical Integer Linear Programming. You have the following problem:

$$\begin{align} Ax+Bx+Cx & \to \max \\ \text{s.t} \quad x,y,z &\ge 0\\ Ax+Bx+Cx &\le T \\ x,y,z &\in \mathbb{Z}\\ \end{align}$$

There are several algorithms available for such problems. Google "branch and bound" or "branch and cut" and you will get to them.

You can picture your problem as follows. Your variables $x,y,z$ decode a grid point in 3d. The constraints cut of hyperplanes, which keeps you left with a set of candidate solutions. In your example this set is finite. You could basically test out all cancidates brute force. But it is more practical to add additional constraints to make the candidate set smaller - or in other words you filter out points. If you relax the condition that $x,y,z$ are integers, then the problem becomes much easier (Linear Programm), because then you know that the optimal point you are looking for is on some "corner" of your candidate set.

Improve this answer
$\endgroup$
  • $\begingroup$ The package lpsolve is the best free option to solve such problems, AFAIK. $\endgroup$ – vonbrand May 11 '13 at 11:21
  • $\begingroup$ @vonband GLPK is better. $\endgroup$ – Bartosz Przybylski May 12 '13 at 20:41
  • $\begingroup$ @A.Schulz Actually, I wanted to find the largest integer value less than T such that it is not satisfied by Ax+By+Cz $\endgroup$ – user77124 May 12 '13 at 21:44
  • $\begingroup$ For those that are interested in IP solvers I can recommend SCIP scip.zib.de/scip.shtml $\endgroup$ – A.Schulz May 13 '13 at 7:14
0
$\begingroup$

Regarding the two-dimensional case, see this answer, which proves the following two results. If $(a,b) = 1$ then every integer $x \geq (a-1)(b-1)$ is representable as $ax+by$ for some $x,y \geq 0$. Also, if $x < ab$ and $a \nmid x$, $b \nmid x$ then exactly one of $x,ab-x$ is representable.

The first result already tells you that without loss of generality, $T \leq (a-1)(b-1)$. Presumably a similar result holds in your three-dimensional case - perhaps you can assume that $T \leq (a-1)(b-1)(c-1)$. The outcome will be an algorithm running in time $\mathrm{poly}(abc)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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