# Integer Programming

I've been having trouble getting started with this problem.

Suppose $x_1,x_2,x_3$ are integers $\geq 0$, satisfying $$21.7x_1-18.2x_2-19.4x_3=5.3$$

Then show $$7x_1+8x_2+6x_3=3+10z_1$$.

(*edit*)where $x_1,x_2,x_3,z_1$ are all integers $\geq 0$

This is from Joel Franklin's Methods of Mathematical Economics page 131.

my attempt: I multiplied the constraint by 10 to get $217x_1-182x_2-194x_3=53$. I found my first basic optimal solution with $x_1=53/217$. This left me with Gomory cut with

$\frac{35}{217} x_2+ \frac{23}{217} x_3 - z_1= \frac{53}{217}$ (where the inverse of inverse of basis matrix was 1/217, and I had to take the positive complements of -182/217 and -194/217 for $x_2,x_3$) as an added constraint.

I am not sure what to do next. Any help would be appreciated. Thanks.

• What is $z_1$ here? – Kieran Cooney Oct 28 '13 at 5:06
• @JosebYosebYi: When you multiplied by $10$, shouldn't you have $217$? – Amzoti Oct 28 '13 at 5:08
• @Amzoti you're correct I changed it. – Joseb Yoseb Yi Oct 28 '13 at 5:15
• I think you need to explain Gomory cut and what you mean by $z_1$. – Amzoti Oct 28 '13 at 5:15
• @KieranCooney It's part of a new constraint -- I think the idea is that since we are considering only integer solutions, the sum of the fractional parts of $x_2$ and $x_3$ should be equal to the sum of an integer ($z_1$) and the fractional part 53/217. – Joseb Yoseb Yi Oct 28 '13 at 5:18

Multiply the first equation by $10$ as you already did and from this subtract the second equation you need to show. Simplify and rearrange to express $z_1$ in terms of $x_1,x_2,x_3$ and constants. It is easy to show that $z_1$ is a sum of products of integers, and hence itself an integer. The part $z_1\ge 0$ follows from the second equation.