0
$\begingroup$

I learnt to solve the task below Linear Programmming is employed. I have tried studying texts to better understand what methods to employ out of the following:

$(A) Gomory's-cut$

$(B) Mixed-Gomory's-cut $

$(C) Branch-and-Bound $

But I am finding it difficult to comprehend any of the three and all the example I see are some how more complex and non related.Is there a way to simplify the problem below given the constraint is just $a,b,c,d,e,f\in \{4,2\} $

\begin{align} a+b+c+d+e+f &= 18, \tag{1} \\ b+d &= 4, \tag{2} \\ e+f &= 8, \tag{3} \end{align}

find $a,b,c,d,e,f$ ?

$\endgroup$
  • 1
    $\begingroup$ we like to use the first letters of the alphabet for constants, and the last letters for variables $\endgroup$ – LinAlg Sep 1 '18 at 13:15
  • $\begingroup$ Any integer program can be solved using (C) branch-and-bound (though it might be very slow—like, thousands of years slow). Any integer program can also be solved using (A) Gomory’s cut—if you add enough rounds of cuts, then you will find the optimal solution. This technique is ALSO very slow. As it turns out, if you combine (A) and (C) together, the result can be very fast. This is (very, very roughly) how IPs are solved today. Look up “branch and cut”. $\endgroup$ – David M. Sep 1 '18 at 13:48
0
$\begingroup$

If all the variable takes value from $\{2,4\}$.

The constraints reduces to

$$a+c=6$$

$$b+d=4 \implies b=d=2$$

$$e+f=8 \implies e=f=4$$

Hence $(a,c) = (4,2)$ or $(a,c)=(2,4)$.

$\endgroup$
  • $\begingroup$ How can an IP have "gaps" like the missing $3$ in $\{2,4\}$? $\endgroup$ – Rodrigo de Azevedo Sep 9 '18 at 12:41
  • $\begingroup$ his constraint has gap isn't it? Did I misread his question? $\endgroup$ – Siong Thye Goh Sep 9 '18 at 12:55
  • $\begingroup$ It has a gap. But is it still an IP? Is the feasible region of an IP the intersection of a convex polytope with $\mathbb Z^n$? Or can it be the union of convex polytopes intersected with $\mathbb Z^n$? Am I missing anything obvious? $\endgroup$ – Rodrigo de Azevedo Sep 9 '18 at 12:59
  • 1
    $\begingroup$ well, that depends on the definiton of IP. For this particular question, we can divide all the variables by $2$ and the gap is gone. $\endgroup$ – Siong Thye Goh Sep 9 '18 at 13:01
0
$\begingroup$

In your case, there is no need to advanced methods, unless you want to practice how to use them. If you only want to solve this specific problem you can do this:

$a+b+c+d+e+f=18$

is

$a+(b+d)+c+(e+f) =18$

so

$a+4+c+8=18$

so

$a+c=6$

since $a,b,c,d,e,f\in \{4,2\} $

you can easily determine integer values for $a,c$ from the last equation.

$\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.