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 #5
| Question | Answer |
|---|---|
| What row from Simplex Tableu do we chose for the Gomory cut (2) | 1, we look for all constrain lines with fractional RHS (right side) 2, we chose the one with "highest difference to rounding" largert fractional part |
| How to calculate the condition for Gomory Cut from Simplex Tableu | a(j) -|a(j)| xj >= b -|b| for all j so for example 1.5x1 -2.25x2 = 1.6 >> 0.5x1 - 0.25x2 >= 0.6 |
| What are 3 types of valid inequalitites | 1, general MIP valid inequalities (like Gomory cut) 2, Valid inequalitities derived from specific constraints (like cover cuts) 3, Problem- Specific valid inequalitites (like Comb inequalitites) |
| Does cutting-plane method by Gomory deliver optimal solution | Yes, but we would need finite BUT possibly VERY LARGE number of Gomory Cuts |
| What is the formula for valid cover cut | ∑w(i)x(i) > C for i∈ U U is subset of elements |
| What is the idea behind the cover cut | we select combination of elements that "are too heavy together" and create an constrain out of it |
| What is the constrain formula for the cover cut | after we discovered U as valid cover cut ∑x(j) <= | U| -1 i∈ U |
| What does separation method algorithmus does | uses u ∈ {0;1} multiplied by x(i) (being coefficient here) to find if x(i) is part of subset U |
| What is goal function of separation method | Zsep(ˆx) = max find the subset that violated condition the most |
| What is the idea of bounding | if the optimal solution in the subproblem can no longer be achieved, the subproblem decomposition is will be avoided |
| What are three things in Branch-and-Bound Problem | 1, processing = computation of bound and using at least one bounding rule 2,generation = generating new successor nodes from given node 3,selection = what nodes are to be proccessed next |
| What is Dakin´s Algorithm (2) | 1, exact method for maximization problems 2,can be used for minimization as well |
| What is upper and lower bound in Dakin´s Algorithm | 1, upper = Solution after LP-Relaxation 2, lower = so far best feasible integer solution |
| How to do branching with Dakin´s Algorithm (3) | 1, we find the fractional variable with fraction closest to 0.5 2, we add x1 >= ceil rounding x1 as a new generation 3, we add x1 <= floor rounding x1 as new generation |
| What do we do in processing a node (3) | 1, prune (stop the node) 2,update best soltuon 3,branch further |
| What do we do in generation of nodes (4) | 1, we find fractional variable with the highest fractional part 2, xj<= floor rounding xj 3, xj >= ceil rounding xj 4, so became the actual xj value constrained |
| What are 3 types of node selection | 1, Depth-First-Search 2, Breadth-First-Search 3,Best-First-Search |
| What does depth-first-search do (3) | 1, go as deep along one branch until it is possible advantage = finds quickly a feasible integer solution disadvantage = may spend a lot of time in bad branch |
| What does breadth-first-search do (3) | 1, process all nodes at one level before going further advantages = explores the tree evenly disadvantages= requires lot of memore, because many nodes remain open |
| What does best-first-search do (3) | 1, process the open node with most promising result advantages = focuses on the best branch so far disadvantages = still requires more memory that depth-first search |
Created by:
semester1.IBWL