Column Generation Problems

I have the following problem. I have a patient scheduling problem that I am solving with column generation due to its complexity. The model basically looks like this. The overall goal is to minimize the total length of stay for patients. The patients have the index \(p\in P\). The patients are treated by nurses \(t\in T\) on days \(d\in D\), or an app with an efficiecny \(\alpha\leq 1\). The decision variable \(x_{ptd}\in \{0,1\}\) indicates whether patient \(p\) is treated by nurse \(t\) on day \(d\), and \(y_{pd}\) whether a patient is treated by the app on day \(d\). The length of stay is the variable \(LOS_p\). Each patient has an arrival day \(Entry_p\) and a number of required treatments \(Req_p\). They can only be discharged when the sum of all previous treatments is \(\geq Req_p\).

The constraints are as follows:

1.  Each nurse has a maximum daily capacity \(C_{td}\), the app has no restriction.
2.  Each patient must receive a nurse treatment on the day of admission, afterwards either by a nurse or the app.
3.  One treatment per day needs to be performed until discharge, determined by the variable \(e_{pd}=1\), indicating eligbility.
4.  There must be at least 3 nurse treatments within a complete 5-day window.
5.  The requirement constraint calculates the sum of all treatments (nurse or weigthed app sessions) up to the current day and sets a discharge variable \(l_{pd}=1\) when this sum is reached.
6.  The length of stay constraint calculates the length of stay based on the entry date and discharge.
7.  Once the discharge variable has taken the value 1, no further treatment can be carried out.
8.  Once a nurse assigned, the patients only recieves treatment from that nurse (variable \(z_{pt}\))

At this point, another important piece of information is relevant. Here, I divide the set of patients into the sets \(P^{Pre},P^{F},P^{Post}\), where \(P=P^{Pre}\cup P^{F}\cup P^{Post}\). \(P^{Pre}\) are patients who are already in the system and who are included as parameter \(x_{ptd}^{Pre}\) from the previous planning period in the nurses' capacity constraints. The patients in set \(P^{F}\) are the patients from the current period whose length of stay is to be optimized. The patients from \(P^{Post}\) are patients in the next planning period who limit the capacity of the nurses and thus provide a more realistic picture  and resource scarcity for the patients from \(P^{F}\) who arrive in the current planning period but cannot be completed there and therefore move into the next one. The sets \(P^{Pre},P^{Post}\) are therefore intended to represent beginning and end-of-horizon shortages that are intended to make the optimization of \(P^{F}\) more difficult. 

The compact model looks like:

\[ \min ~~\sum_{p\in P^{F}\cup P^{Post}}E_p LOS_p \]

s.t.

\[ \sum_{p \in \mathcal{P}} x_{ptd} + \sum_{p \in \mathcal{P}^{\text{Pre}}} x_{ptd}^{\text{Pre}} \leq N_{td} \quad \forall t \in \mathcal{T}, d \in \mathcal{D} \]

\[ \sum_{t \in \mathcal{T}} x_{ptd} + y_{pd} = e_{pd} \quad \forall p \in \mathcal{P}, d \in \mathcal{D}  \]

\[ x_{ptd} \leq z_{pt} \quad \forall p \in \mathcal{P}, t \in \mathcal{T}, d \in \mathcal{D}  \]

\[ \sum_{t \in \mathcal{T}} z_{pt} = 1 \quad \forall p \in \mathcal{P}  \]

\[ LOS_p = \sum_{d \in \mathcal{D}} d \cdot l_{pd} - Entry_p + 1 \quad\forall p \in \mathcal{P} \text{, if } \sum_{d \in \mathcal{D}}\]

\[ \sum_{t \in \mathcal{T}} x_{pt (Entry_p)} = 1 \quad \forall p \in \mathcal{P}  \]

\[ Req_p l_{pd}  \leq \sum_{j = Entry_p}^{d}\left( \sum_{t \in \mathcal{T}}  x_{ptj} +  \alpha  y_{pj} \right)\quad \forall p \in \mathcal{P}, d \in \mathcal{D} \]

\[ l_{pd} \leq \sum_{t \in \mathcal{T}} x_{ptd} \quad \forall p \in \mathcal{P}, d \in \mathcal{D}  \]

\[ \sum_{d \in \mathcal{D}} l_{pd} = 1 \quad \forall p \in \mathcal{P}^{\text{Focus}}  \]

\[ \sum_{d \in \mathcal{D}} l_{pd} \leq 1 \quad \forall p \in \mathcal{P}^{\text{Post}}   \]

\[ e_{pd} = 0 \quad \forall p \in \mathcal{P}, d \in \mathcal{D} , d < Entry_p  \]

\[ e_{p (Entry_p)} = 1 \quad \forall p \in \mathcal{P} \]

\[ \sum_{j=Entry_p}^{d-1} l_{pj}+e_{pd}  = 1\quad \forall p \in \mathcal{P}, d \in \mathcal{D} , d > Entry_p \]

\[ \sum_{j = d}^{d + 5-1} \sum_{t \in \mathcal{T}} x_{ptj} \geq 3 - 3 \left( 5 - \sum_{j = d}^{d + 5-1} e_{pj} \right) \quad \forall p \in \mathcal{P}, d \in \left\{ 1, \ldots, \left|\mathcal{D}\right|- 5+1 \right\}\]

\[ e_{pd}, l_{pd},x_{ptd}, y_{pd}, z_{pt} \in \{0, 1\}\quad\forall p \in \mathcal{P}, d \in \mathcal{D}, \forall t \in \mathcal{T}  \]

\[  LOS_p \in \mathbb{Z}_{\geq 0}\quad \forall p \in \mathcal{P}, d \in \mathcal{D}\]

According to the Dantzig-Wolfe reformulation, this results in the following MP and the patient-specific SPs. The capacity constraint flows into the MP, while the remaining constraints flow into the SPs. Here, \(\lambda_{pv}\) is the binary decision variable and \(\chi_{ptd}^v\) and \(\mathbb{L}_p^v\) are the parameters for \(x_{ptd}\) and \(LOS_p\).

\[MP \quad \min \sum_{p\in P^{F}} \sum_{v \in {V}(i)} \mathcal{LOS}_p^{v} \lambda_{pv}\]

s.t.

\[\sum_{p\in P^{F}\cup P^{Post}} \sum_{v\in {V}(i)} \chi^v_{ptd} \lambda_{pv} + \sum_{p\in P^{Pre}} x_{ptd}^{Pre}\leq C_{td}\quad \forall t,d \quad (\pi_{td}) \]

\[\sum_{v \in {V}(i)} \lambda_{pv} = 1 \quad \forall p \quad (\eta_p) \]

\[\lambda_{pv} {\geq 0}\]

And the SPs

\[SP(p)\quad \min E_p\cdot LOS_p - \sum_{j \in J} \sum_{t \in T} \pi_{td} x_{ptd} - \eta_p\]

s.t.

Remaining Constraints

Here, \(E_p\) indicates whether patient \(p\) is part of \(P^{F}\) (\(E_p=1\)) or \(P^{Post}\) (\(E_p=0\)).

Now I have implemented the whole thing as a Price-n-Branch heuristic. See the code here:

I initialize the model with trivial columns for the patient sets \(P^{F}, P^{Post}\) and with the parameters \(x_{ptd}^{Pre}\). I assign all \(P^{F}\) patients with a Big-M objective coefficient for the objective function \(\mathbb{L}_p^1\) and nurse assignments of zero for all patients. The first column looks like this:\([M,\chi_{ptd}\equiv 0,1]^T\) for the focus patients and \([0,\chi_{ptd}\equiv 0,1]^T\) for the post patients.

I have now solved the model for my own small instances and compared it with Gurobi .optimize(), and often find the same solution. But upon closer look, they do differ significantly. While the compact model naturally optimizes the focus patients and therefore also provides them with a feasible schedule, this is also the case for the post-patients. These are not optimized, of course, but must still be given a feasible schedule within the model constraints. Accordingly, I can have a post-optimization schedule generated for both patient groups. Unfortunately, however, the situation is different for the CG. Here, only columns for the focus patients are generated. In my opinion, this is due to the interaction between the duals and the objective function. The dual values \(\pi_{td}\) are all non-positive and mostly equal to 0. The dual values \(\pi_i\) are always non-negative for the focus patients (with larger values in the first iterations and then decreasing) and equal to zero for the post patients. If we now look at the objective function of the post patients in the subproblem, the whole thing reduces to \(-\sum_{t,d}\pi_{td}x_{itd-\mu_i}\). If \(\\) is equal to zero and \(\\leq 0\), then the reduced costs are never less than zero and therefore no new columns are generated, since the original costs of the focus patients in the master problem are equal to zero due to their non-existence in the MP objective.

Conclusion: while the compact model also generates schedules for the post-patients, CG does not, and thus their usefulness as resource blockers is also eliminated. Now to my question. Did I make a mistake in the decomposition, or is this approach simply flawed for column generation?

Now to part 2 of the question. If I initialize the post-patients with a high Big-M, i.e., objective function coefficient, then the algorithm will of course also find columns for the post-patients. These are usually much better, which is why columns appear in the final solution in later iterations. However, sometimes it happens that even after, for example, five iterations, no new column is found, and then an initial column appears in the final integer solution, thus inflating the final objective function value of the focus patients by the Big-M coefficient of the start columns. This behavior can be achieved by deleting self.E[p] in the line 42 and 58 in the masterproblem.py file.