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$
2
  • 1
    $\begingroup$ we like to use the first letters of the alphabet for constants, and the last letters for variables $\endgroup$ Commented Sep 1, 2018 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$ Commented Sep 1, 2018 at 13:48

2 Answers 2

Reset to default
1
$\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$
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$
4
  • $\begingroup$ How can an IP have "gaps" like the missing $3$ in $\{2,4\}$? $\endgroup$ Commented Sep 9, 2018 at 12:41
  • $\begingroup$ his constraint has gap isn't it? Did I misread his question? $\endgroup$ Commented Sep 9, 2018 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$ Commented Sep 9, 2018 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$ Commented Sep 9, 2018 at 13:01

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.