Implementation of sub-problem aggregation makes the problem unfeasible
Awaiting user inputI am facing a weird problem. I am currently implementing a column generation heuristic with aggregated sub-problems (for those that are identical). I use this model decomposition and this aggregation approach.
In my code implementation, I have the Set of Patients `P`, their entry dates `Entry_p`, and required treatments `R_p`. Now, I check whether there are patients with identical combinations. Based on this, I created the new set `N_c` and the updated entries `Entry_p_c` and `R_p_c`. So for instance, the set `P` has a length of 20 and the patients 2 and 19 have the same characteristics, `N_c` has a length of 19 and the entry and treatment values remain the same for each entry until 19, but since this patient already existed before, the values of the "original" patient 20 are now in the 19th place. Then I also have `Nr_c`, which indicates how many patients have this profile. So far so good. Here comes the tricky part. I initialize the restricted master problem with a feasible solution from the compact solution (I solve the compact model to a gap of 90% and then take the values. I know there are better ways but that's the way it is right now. Any other ideas are also appreciated). However, since the lengths of the patients `P` in the compact model and the profiles `N_c` in the column generation don't match, I deleted the duplicate values from the obtained solution dict, to match the length. I run the `startSol` function, which then replaces the initialized master problem with the values from the starting solution. Since some profiles occur more than once, I multiply each value by the number of patients in each profile. By doing this, somehow, the master problem becomes infeasible, making it impossible to obtain the dual values for the first iteration. However, this occurs only for values of `P>26`. For smaller `P` values, this problem does not happen. I also computed the `IIS`, as Seen here:
IIS: lambda(19): lmbda[19,1] + lmbda[19,2] + lmbda[19,3] = 2.0
p_max(2,6): 100.0 lmbda[1,2] + 100.0 lmbda[1,3] + 100.0 lmbda[2,2] + 100.0 lmbda[2,3]
+ 100.0 lmbda[3,2] + 100.0 lmbda[3,3] + 100.0 lmbda[4,2] + 100.0 lmbda[4,3]
+100.0 lmbda[5,2] + 100.0 lmbda[5,3] + 100.0 lmbda[6,2] + 100.0 lmbda[6,3] + 100.0 lmbda[7,2]
+ 100.0 lmbda[7,3] + 100.0 lmbda[8,2] + 100.0 lmbda[8,3] + 100.0 lmbda[9,2] + 100.0 lmbda[9,3]
+ 100.0 lmbda[10,2] + 100.0 lmbda[10,3] + 100.0 lmbda[11,2] + 100.0 lmbda[11,3] + 100.0 lmbda[12,2]
+ 100.0 lmbda[12,3] + 100.0 lmbda[13,2] + 100.0 lmbda[13,3] + 100.0 lmbda[14,2] + 100.0 lmbda[14,3]
+ 100.0 lmbda[15,2] + 100.0 lmbda[15,3] + 100.0 lmbda[16,2] + 100.0 lmbda[16,3] + 100.0 lmbda[17,2]
+ 100.0 lmbda[17,3] + 100.0 lmbda[18,2] + 100.0 lmbda[18,3] + 2.0 lmbda[19,1] + 100.0 lmbda[19,2]
+ 100.0 lmbda[19,3] + 100.0 lmbda[20,2] + 100.0 lmbda[20,3] + 100.0 lmbda[21,2] + 100.0 lmbda[21,3]
+ 100.0 lmbda[22,2] + 100.0 lmbda[22,3] + 100.0 lmbda[23,2] + 100.0 lmbda[23,3] + 100.0 lmbda[24,2]
+ 100.0 lmbda[24,3] < 1.0
LP: p_max(2,6): 100 lmbda[1,2] + 100 lmbda[1,3] + 100 lmbda[2,2]
+ 100 lmbda[2,3] + 100 lmbda[3,2] + 100 lmbda[3,3] + 100 lmbda[4,2]
+ 100 lmbda[4,3] + 100 lmbda[5,2] + 100 lmbda[5,3] + 100 lmbda[6,2]
+ 100 lmbda[6,3] + 100 lmbda[7,2] + 100 lmbda[7,3] + 100 lmbda[8,2]
+ 100 lmbda[8,3] + 100 lmbda[9,2] + 100 lmbda[9,3] + 100 lmbda[10,2]
+ 100 lmbda[10,3] + 100 lmbda[11,2] + 100 lmbda[11,3] + 100 lmbda[12,2]
+ 100 lmbda[12,3] + 100 lmbda[13,2] + 100 lmbda[13,3] + 100 lmbda[14,2]
+ 100 lmbda[14,3] + 100 lmbda[15,2] + 100 lmbda[15,3] + 100 lmbda[16,2]
+ 100 lmbda[16,3] + 100 lmbda[17,2] + 100 lmbda[17,3] + 100 lmbda[18,2]
+ 100 lmbda[18,3] + 2 lmbda[19,1] + 100 lmbda[19,2] + 100 lmbda[19,3]
+ 100 lmbda[20,2] + 100 lmbda[20,3] + 100 lmbda[21,2] + 100 lmbda[21,3]
+ 100 lmbda[22,2] + 100 lmbda[22,3] + 100 lmbda[23,2] + 100 lmbda[23,3]
+ 100 lmbda[24,2] + 100 lmbda[24,3] <= 1
What irritates me is that in the `.lp` file, this constraint has a `<=` sign, in the `IIS`, however, it is a `<` sign. Any idea why my aggregated MP becomes infeasible even with a feasible solution to the compact model? If I don't apply this aggregated approach, the problem is solvable for `P` values greater than 26, so it must be a problem with how I add the feasible first column.
The code for the aggregated version can be found here, and for the non-aggregated version here.
Already posted here:
-
Hi Nico,
Just in case it is relevant: the default lower bounds of variables are 0 (and this default is not printed in LP or IIS). The reason I highlight this is that it is simple to see why the IIS is infeasible if you are aware of this fact.
As for the "<" in the ILP file, this is quite bizarre and I can't reproduce it. The equality sign hasn't accidentally been deleted? Rest assured the solver is not using a < constraint (because it can't).
- Riley
0
Please sign in to leave a comment.
Comments
1 comment