Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
PDS #6
| Question | Answer |
|---|---|
| What are two combination method of node selection | 1, Depth-First + Best-First Search 2, Beam Search |
| How does Depth-First + Best-First Search method works (2) | 1, we use Depth-First to find a first feasible integer soltuon 2, then we change to Best-First to explore the node further |
| How does Beam Search works (2) | 1, we use breadth-first search 2, at each level we continue with only x(beam width) number of best nodes so far |
| What is difference between Branch-and-Bound and Cutting-Plane-Method | Cutting Plane = cut away a part at the edge of the LP-feasible but MIP infeasible domain B&B = splits feasible region into subproblems as "middle strip" |
| What is Branch & Cut Method (2) | 1, combination of branch & bound + cutting plane method 2, in each node, the LP relaxation is strengthened by adding violated valid inequalitites |
| What is the trade-off in B&C method (2) | 1, more cuts >> strong bound and therefore smaller tree for B&B 2, fewer cuts >> LP Relaxation is faster to solve because we have less contrains |
| What is true about model with a lot of constrains or variables (2) | 1, they may be faster to solve even if they look larger because they have smaller integrity gap 2, integrity gap = difference between Solution of LP-Relaxation and Whole Integer Solution |
| What are 4 components of Bin Packing B&B | 1, non-binary branching 2, priori known structure of the search tree 3,analytical determination of a lower bound 4, no further component (heuristic , fix var ect) |
| What does non-binary brancing in Bin Packing B&B means | we may have more than two nodes xj>= |xj| & <= |xj| |
| What does a priori known structure of the search tree means in B&B Bin Packing | the items are sorted not-increasingly w(k) >= w(k+1) |
| What is analytical determination of a lower bound | zLB = 1/C * ∑(w(i)) .. rounded up not result from LP-Relaxation |
| What is generation of nodes in B&B Bin Packing (3) | 1, item can be placed in one of the used bin with enough remaining capacity 2, we can also put the item into new bin 3, in each node we hae list of used bins with their free capacity |
| What is selection of nodes in B&B Bin Packing | we use depth-first seearch |
| How to calculate analytical upper bound for recent node | zLB(Pi)=n(Pi) + [1/C * (∑w(i) - C(Pi) ] n(Pi) ... bins already used ∑w(i) .. the weight that still has to be packed C(Pi) ... free space in already opened bins |
| What is global lower band in Branch & Bound Problem | best LP-Relaxation solution from so far unprocessed nodes |
| What is global upper band in Branch & Bound Problem | best feasible solution so far |
| When should we Branch in B&B Problem | node has infeasible solution with LP-Relaxation better than global upper band |
| When should we Bound in B&B Problem (2) | 1, we have feasible solution 2, we have unfeasible solution but current global upper is better (we cannot improve the solution) |
Created by:
semester1.IBWL