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 #7
| Question | Answer |
|---|---|
| When do we use Heuristics | when the problems became very costly to find the optimal solution |
| What does selection of method depedent on (3) | 1, available software 2,cost-benefits consideration 3,complexity of the problem |
| What are polynomial time algoritms | algorith with O(n^c) time like n^2 or n^3 "timely manageble" NOT n! or c^n |
| What is true about (M)IP problems (3) | 1, some dont have known exact POLYNOMIAL TIME algorithm 2,some fullfiel integrity (whole integer solutions) automatically like MCFP 3, in most cases optimalization problem can be solved in polynomial time |
| What are reasons for Heuristic usage (5) | 1, they are often simplier / easier 2, constrained computation time or memory 3, real-world problems may be too difficult to solved exactly 4, can help understand decisions 5, even exact procedurs may use heuristic component |
| What are 3 types of Heuristics | 1, Construction Heurstistics = generate a first solution 2, Improvement Heuristic = improve initial solution until a stopping criterio is met 3,Metaheuristic = high-level algorithm |
| How does Greedy Algorithm works (2) | 1, start with no or initial solution 2,select the best-looking next step |
| What are two greedy algorithm for Facility Location Problems | 1, Add Heuristic 2,Drop Heuristic |
| How does Add Heuristic works (3) | 1, Initial Solution >> No location is selected 2,Iterate >> add a single location with the largest saving compared to allocation costs & fixed cost of opening a new location 3, Terminate >> No more improvement possible |
| How does Drop Heuristic works (3) | 1, Initial Solution >> all location are selected 2, Iteration >> Removed a single location based on difference between fixed costs and increase of allocation costs of closing a location 3, Terminated >> No possible improvements |
| What are Notations for Add & Drop FLP (5) | 1, I = set of all costumers 2, J = set of all locations 3, S⊆J = currectly selected location 4, N⊆J = location excluded from the solution 5, E⊆J = location forced open in the solution |
| What are starting point of Add & Drop for FLP | Add Heuristic >>> S=N= ∅ Drop Heuristic >>> S=J ; E= ∅ |
| What is the objective function of Add & Drop Heuristics | ci(S) = min{ c(i,j) : j ∈ S } |
| What is difference between Adjacency Matrix and Incidence Matrix | Adjecency Matrix = both row and column nodes >> 1 - nodes connected , 0 - otherwise Incidence Matrix = node rwo, column node/edge >> 1 outcoming, -1 incoming, 0 therwise |
| What is difference between Undirected and Directed Graph | Undirected - connection do not have a fix direction Directed - connections go only one way |
| What is a difference between edge & arc | edge - connection between nodes arc - edge with a direction |
| What is (in/out)degree of a node (3) | Degree of a node = number of incidence edge (to how many other nodes is connected) Outdegree = Number of arcs outcoming Indegree = Number of arcs incoming |
| What is Binding Constrain | the considered solution has equality with the constrain |
| What can I forgot when marking corners of a LP | the (0,0) and other at 0 point |
| What does Domain mean | which value are decision variables allowed to take x ∈{0,1} , x∈Z+ etc |
Created by:
semester1.IBWL