Dear support team,
I hope you are doing well.
I am currently working on the scheduling problem where I am trying to solve that via column generation. For simplicity, suppose the problem is similar to the bin packing problem, (I omitted some of the remaining constraints), in which the problem is decomposed such that the master contains set-partitioning constraints and packing constraints keeping in the subproblem. I should note the packing polytope is non-identical and there are various capacities to assign the tasks. The decomposed problem is in the following form:
- The master problem:
\text{Min} \ z_{mp} \ = \sum_{s} \sum_{p=1}^{P_s} \lambda_{s}^p
\text{S.t:}
\sum_{s} \sum_{p=1}^{P_s} z_{is}^p \lambda_{s}^p = 1 \quad \forall i \in \text{Tasks}
\sum_{p=1}^{P_s} \lambda_{s}^p \leq 1 \quad \forall s \in \text{Machines}
\lambda_{s}^p \in \mathbb{B}^+
where (y_{s} \ = \sum_{p=1}^{P_s} \lambda_{s}^p ).
- The subproblem:
\text{Min} \ z_{sp} \ = \{ (\sum_{s} y_{s}) - (\text{Reduced cost}) : \sum_{i} w_{i} x_{i,s} \leq cap_{s} y_{s} \}
x_{i,s}, y_{s} \in \mathbb{B}^+
As the problem is decomposed based on the machines and if the machines were identical, it was straightforward to have a unique subproblem to generate the patterns that were acceptable on all of the machines. Then it was possible to omit the index s on the subproblem. Now w.r.t the fact that the machines are non-identical, I am struggling to write the subproblem in the correct format. There are two options:
- Defining the subproblem in an aggregate form to capture the different patterns
- Defining the subproblem for each machine, is equal to saying there are j separated subproblems
What I am still trying now is based on the first manner.
knapsack_obj.. z_sub =e= sum((s), y(s)) - sum((i,s),master_demand.m(i)*x(i,s));
knapsack_constraint(s).. sum(i, w(i)*x(i,s)) =l= CT(s)*y(s);
By the above definition, the problem can be solved without throwing any error and producing a suboptimal solution. At the moment ensuring the correct definition and solving procedure is enough to me, specifically, the aggregate form of the subproblem.
Now, my questions are:
- Are the first and second manners I mentioned to define the subproblem correct?
- Can what I wrote as the
knapsack constraintto aggregate the appropriate patterns really reflect the decomposition of the problem? - May we omit the convexification constraint from the master w.r.t. the minimizing form?
- Is it possible to write the second manner in GAMS? If so, can you advise me?
All the best
Abbas