Matheuristics: Fix-and-Relax vs. Fix-and-Optimize

Question 1

What is the motivation behind applying Fix&Relax to CLSP?

Answer 1

CLSP is NP-hard

Most computational effort is required to determine the optimal setup pattern

Given a setup pattern, the remaining problem (i.e., determining corresponding production quantities and inventory levels) can be solved using the simplex algorithm.

Question 2

What is the idea of the Fix&Relax heuristic?

Answer 2

Definition of subproblems via

• –Fixation (of a subset of binary setup variables)
• –Optimization (of a small subset of binary setup variables, of all real-valued decision variables over the complete planning horizon and all products)
• – Relaxation of the remaining subset of binary setup variables

Solving each subproblem to (sub)optimality

Question 3

Was ist die Besonderheit zwischen den drei Mengen KT^opt, KT^fix, KT^rel bei der F&R-Heuristik?

Answer 3

Geschnitten miteinander ergeben sie immer eine leere Menge (d.h. sie haben keine Elemente gemeinsam).

Vereinigt ergeben sie die komplette Ausgangsmenge KT.

Question 4

Idea of Fix&Optimize-Heuristik

Answer 4

Definition of subproblems via

FIXATION
– of a large subset of binary setup variables

OPTIMIZATION

• • of the remaining smaller subset of binary setup variables
• • of all real-valued decision variables over the complete planning horizon, all products and resources

Solving each subproblem to (sub)optimality

Question 5

What is the main difference regarding the sets of F&O compared to F&R?

Answer 5

F&O only has two sets KT^fix and KT^opt, which are disjunctive (disjunkt, also haben keine Schnittmenge).

The adding of those boths sums gives back KT.

F&R has three sets, in addition to the two named above it also uses a KT^rel(axed) set. Those are also disjunctive and together add up to the entire set KT.

Question 6

What is a prerequirement to starting the F&O-heuristic?

Answer 6

Initialization through providing/determining an initial solution. THis can be done through either F&R-heuristic or by setting gamma-“strich”_kt = 1 for all k and t.

Question 7

What are possible decomposition strategies for F&O?

Answer 7

Product-oriented only

Period-oriented only

Product-oriented first, afterwards period-oriented

Question 8

What is the general rundown of the F&O heuristic?

Answer 8

Iterative improvement of current solution via decomposition strategies until stopping criterium is met

Question 9

What are stopping criteriums in F&O?

Answer 9

Maximum number of iterations

Local optimum is reached (meaning Z^l = Z^(l-1))