Summary Flashcards
Cut-and-Fix
Fix all Y that are 0 or 1 in LP-Relaxation
Relax-and-Fix
Divide Variables into Subsets U and Sets Q. Ex. 4 Subsets of 5 each. First impose first 10 Variables are binary. Solve. Second fix 5 Variables of Q1 to obtained value. Impose Q2u U2 (5-15) binary. Repeat.
RINS (Improvement)
Solve LP Relax. get feasible Sol. set all y that are the same in both solutions to that value.
Local Branching (Improvement)
Start from feasible solution. Solve MIP where not more than k variables differ from their value in the feasible solution.
Exchange (Improvement)
Divide variables into Groups. Fix Variables of one group to value obtained in feas. sol. Relax others to take binary values.
PROB
- LS
- WW (LS but without production costs)
- DLSI (LS but can only produce at capacity or nothing)
- DLS (DLSI without inital stock)
CAP
- C: Capacities Ct vary over time
- CC: Capacities Ct constant
- U: Uncapacitated
VAR
- B (Backlogging)
- SC (Start-Up Costs)
- ST (Start-Up Times)
- LB (Minimum Production Levels)
- SL (Sales and Lost Sales)
- SS (Safety Stocks)
B (Backlogging)
You can satisfy demand r later than required at a cost b.
SC (Start-Up Costs)
Costs g for set-up for machine y in t if z = 1) (Make sure that set-up happens in t but not in t-1)
ST (Start-Up Times)
Capacity is reduced by ST in t. Only occur if there is a start-up z = 1
LB (Minimum Production Levels)
Lower Bounds for production
SL (Sales and Lost Sales)
Problem -> Profit maximization, Amount v can be sold for c
SS (Safety Stocks)
Keep a safety stock
EVPI
Expected Value of Perfect Information
EVPI = WS - SP
WS = Wait and See Solution, Solution we would get if we could postpone the decision to take it after a scenario has realized
VSS
Value of Stochastic Solution
Value & Advantage of solving stochastic problem instead of deterministic
VSS = SP - EEV
1. Solve EV (Expected Value of of demand)
2. Substitute x into SP (EEV)
LUSS
Loss of using the skeleton solution
Does the deterministic solution produce the right non-zero variables?
LUSS = SP - ESSV
1. Solve EV problem -> obtain first stage variables
2. Fix all obtained vars that are zero and solve SP -> obtain first stage solutions
3. Substitute solutions into SP and solve (ESSV)
LUDS
Loss of using the deterministic solution
Can the deterministic solution be upgraded to become good or optimal for the SP?
LUDS = SP - EIV
1. Solve EV -> obtain first stage solutions
2. Impose x >= x and solve SP -> obtain first stage solutions
3. Substitute solutions into SP and solve (EIV)
Constant trend
- Elementary: p(t+1) = y(t)
- Simple moving average
- Weighted moving average
- exp. smoothing: p(3) = αy(2) + (1-α)p(2)
Linear trend
pt(t) = a(T) + b(T)*t
- Elementary: a(T) = y(T), b(T) = y(T) - y(T-1)
- Holt-Method
Seasonal Variations with periodicity M
- Elementary: M = 12; p(25) = y(25-12) = y(13)
- Winters: a(t), b(t), s(t+M)
a(0) = average over all periods
b(0) = (av. last period - av. first period)/(T-M)
