Bender-decomposition---a-toy-model

This is a toy model for bender decomposition.

Detailed steps have been written in code files as annotations. For the sake of completeness, main ideas are described as follows:

Step 1:

1.0. establish the master problem
1.1. add initial constraints
1.2. solve master problem
1.3. get solutions(x,\ita) for the subproblem

Step 2:

for k-th scenarios:
    2.0. establish the k-th subproblem
    2.1. solve the subproblem to verify whether the current solution (x,\ita^k) is optimal
        if yes:
            done
        else:
            2.1.1: if subproblem is infeasible:
                add feasibility constraints to master problem
            2.1.2: if the objective value of the subproblem is greater(for maxmizing problem) 
            or smaller(for minimizing problem) than \ita:
                add optimality constraints to master problem

Step 3:

3.1. solve master problem again, and repeat above iterations untill \ita is equal to 
the objective values of the subproblem

The most confused part, in my opinion, is part 2 about HOW to verify the optimality of current solution, HOW to identify feasibility constraints, and HOW to find out optimality constraints.

For starters, there are some reading materials, which may help you a lot: (I LOVE THE FIFTH ONE!! It has wonderful pictures explaining details!!!!)

ANY QUESTIONS ARE WELCOMED ~ PLEASE SEND ME EMAIL

chendu2017/benders_decomposition_a_toy_model

Bender-decomposition---a-toy-model