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 #4
| Question | Answer |
|---|---|
| What is the notation and decision variables in Matching Problems | c(i,j) ...cost (perfect match) or profit (matching) of employee i and j working together |
| What are decision variables in Matching Problems | x(i,j) ∈ {1 i,j working together 0 otherwise} |
| What are conditions in Matching and Perfect Match | Matching >> ∑x(i,j) <=1 Perfect Match >> ∑x(i,j) = 1 |
| What are 3 types of Set Problems | 1, Set partitioning = every element must be contained exactly once (b(i,j)=1) 2, Set packing = every element can be contained at most once (b(i,j)<=1) 3, Set covering = every element must be contained at least once (b(i,j)>=1) |
| What are objective of the 3 types of set problems | Set Partitioning >> cost minimization (and have every element exactly once) Set Packing >> profit maximization (and having every element at most once) Set Covering >> cost minimization (and having each element at least once) |
| What are notation for Set Problems(4) | 1, M = {1,..n} set M with all the elements 2, M(j) ,, subset j containing some of the elements 3,c(j) = cost/profit of subset j 4, b(i,j) = 1 or 0 if element i s in subset j |
| What is generalized incidence matrix for Set Problems | Subset are rows M1, M2, ... Mn elements are columns 1 2 3 n 1 if element inside of subset / 0 otherwise |
| What is notation for Facility Location Problem (4) | 1, I∈{1,2, ..n} set of all costumers 2, J∈{1,2...n} set of all facilities 3, c(i,j) .. cost of using facility j to serve costumer i 4,f(j) .. cost of opening facility j |
| What are 2 decision variables for Facility Location Problem | 1, y(j) ∈{0,1} .. should we open facility j 2, x(i,j) ∈{0,1≠ .. should we serve i from j |
| What are constrains for Facility Location Problem | x(i,j) <= y(j) ... from facility j can be served only if its open |
| What is objective function for Facilitiy Location Problem | z* = min ∑f(j)y(j) + ∑∑ c(i,j)x(i,j) |
| How to write matematically for facility to be opened it must serve at lease two costumers | ∑x(i,j)>= 2y(j) ∀j∈J |
| What is LP (Linear Programming) -Relaxation of MIP (Multiple Integer Programming) (3) | 1, change Integral Problem into Linear Problem with x^n ∈ R 2, also binary variable can se set as float between 0 and 1 3, LP Relaxation give us upper bound for optimal solution |
| Can we use LP Relaxation for solution | Not directly, NO ROUNDING UP/DOWN |
| What is convex hull (3) | 1, X = conv(s) 2, all extreme points of X =conv(S) are integer 3, complete description is NOT KNOWN in general |
| What is the idea of Cutting Plane Method | adding valid inequalitites so that the feasible region converge toward convex hull |
| What is the sequence for cutting plane method (5) | 1, Solve the LP-Relaxation with x̂ as solution 2, Check if x̂ has only integer values yes > x̂ is optimal / no > step 3 3, Determine a violated valid inequality 4, add violated valid inequality as constrain 5,repeat from step 2 |
| What do we do in step 3 in cutting plane method (2) | 1, a^⊤ x <= b ∀x∈S but a^⊤x̂ >b 2, cutting as much as possible from feasible region but not cutting out any integer solution |
Created by:
semester1.IBWL