Forum Discussion
A specific separation procedure, $(l,S)$ Inequalities, to solve the lot-sizing problem
Dear support team,
I have tried to use a specific separation procedure, $(l, S)$ Inequalities, to solve the lot-sizing problem proposed in the references, like Algorithm and formulations for lot sizing problems by Laurence Wolsey. The compact formulation is very straightforward as it is an uncapacitated lot-sizing problem, known as LS-U. The compact formulation contains standard flow/inventory constraints together with a setup constraint. The objective is to minimize the costs of production rate, inventory holding, and setup time.
$$ \sum_{j \in L \backslash S} x_{j} + \sum_{j \in S} d_{(j,l)} y_{j} \geq d_{(1,l)} $$
Based on the mentioned references, the above inequality was derived from the following:
$$ \sum_{j \in S} x_{j} \leq \sum_{j \in S} d_{(j,l)} y_{j} + s_{l} $$
where, n stands for planning periods, 1<= l <= n, L={1,⋯,l} , and S subset of L.
My first question is:
- How is the above first inequality actually derived from the second, and what is the benefit of such a rewritten form?
From the implementation side, this link is the only one I have found so far. As this algorithm was implemented in the Mosel language, and I do not have any experience working with that, I was wondering if:
- Is it possible to translate the follwoing part of the code into its appropriate mathematical form?
! Generate the violated inequality
if ds < D(p,1,l) - EPS then
cut(ncut):= sum(t in 1..l)
if(solprod(p,t)<(D(p,t,l)*solsetup(p,t))+EPS, produce(p,t),
D(p,t,l)*setup(p,t)) - D(p,1,l)
cutid(ncut):= 1
type(ncut):= CT_GEQ
ncut+=1
end-if
end-do- Also, it would be great if there exists any equivalent Python code to see and benchmark
All the best
Abbas
4 Replies
Dear Abbas,
Thank you very much for contacting our community. Let me answer your questions in the same order:
- We could not find the second inequality in the paper of Laurence Wolsey. Most likely, it is either an aggregation of constraints in the original ULS formulation, so not a cut, or it is equivalent to to the (l,S) cut, in the sense that flow conservation equations can be added to obtain the one or the other.
- The mentioned Mosel code does indeed generate violated (l,S) inequalities. The produce variables are the $x$ variables and the setup variables are the $y$ variables in your expression. The if statement is responsible for defining the subset $S$ and its complement $L \backslash S$. That is, the summation in the Mosel expression represents the two summations in the (l,S) inequality.
- For an example of how to generate and add cuts in a callback using python, my colleagues Bruno Vieira and Susanne Heipke managed to translate the same Mosel model into similar python code, which I am attaching here (els.py). Notice that for this exemplary small problem instance, the Python callback overhead may offset the node reduction benefit from the cuts, so you may not see meaningful speedup until you scale to larger instances where node count dominates solve time.
Best regards,
Christian Raack
Dear Christian,
Many thanks for your comments as well as the provided link. I agree with you that it is either an aggregation of constraints in the original ULS formulation, so not a cut. I also could not find any further information, maybe a bit more on the `production planning by mixed integer programming book`.
Now, let me explain more regarding the issue I have encountered. Based on what the authors mentioned, the first or second inequality, besides the original problem constraints, I mean flow/inventory and setup constraints, should be able to describe a complete linear combination of the original problem convex hull. I totally talk about linear programming, not a MIP. Please, correct me if my inference from the references is being wrong.
Also, I modified the provided code to accommodate my problem. (The Wolsey example in PPBYMIP). Please, see the attached Basic_file. In the MIP model, the objective is 736000, and its dual bound (linear relaxation) would be 712188. I have tried solving your provided example by relaxing the integrality constraint and observed that the model and its separation procedure cannot reconstruct the original solution space. While I expected the code to do that. Actually, it cannot separate any new cuts and add them to the model. The same behaviour goes to my problem, see the attached file example_PPBYMIP, and this is where I am getting stuck in understanding how this cut can be added to the model.
As a second attempt, I managed to use the MIP mechanism of the solver to add these kinds of cuts by changing the value of the cutdepth parameter and adding an integrality constraint. However, the result did not change. Also, I tried to use the first form of the proposed cut and add them to the model in the original solution space as a constraint in the compact formulation. In this case, everything goes well, but there are actually an exponential number of such cuts even for my tiny example!!!
I was wondering if, how I can fix the issue.
Best regards
Abbas
Hi Abbas,
thank you for coming back to us. We are not a 100% sure what your intention is and where the problem lies. I will just provide a few comments and hope these help.
- Back to the two inequalities you are mentioning in your first question. As I assumed these are identical. Both represent the same (l,S) inequality. Summing over the flow conservation constraints (involving x and s variables) for $j \in L$ in the standard ULS formulation from the Wolsey paper and adding them to the first inequality gives the second.
- Now it depends on which model you are solving. The literature about different variants of LS is rich and this is not the place to discuss all of them. The mentioned Mosel model and python sibbling are variants of ULS in the space of the x and y variables. That is, only the first inequality can be used with this model. The model further imposes capacity constraints, so it is not exactly the uncapacitated ULS variant your are referring to and that you seem to implement in your examples.
- The Mosel and python code are just showcasing the use of user cutting planes. They are are based on a simple separation procedure for (l,S) inequalities, choosing the set S greedily such as to minimize the left hand side, maximizing potential violation. It is not said at all that using these additional cuts with this separation procedure actually accelerates the solve. Xpress has its own internal cutting place procedures. It might be very effective solving your lot sizing problem without any "help". (You can switch off all Xpress cuts using cutstrategy=0.)
- When you remove the integrality constraints the problem becomes an LP. Xpress still triggers an MILP solve because you have an optnode callback set. However, without doing anything else, the root LP solution is detected as globally feasible very early by some heuristic and the solve will terminate with that solution without actually calling your separation routine. If you want to mimic a pure cutting plane procedure with only your cutting planes, you have to switch off all heuristics (heuremphasis=0). This should trigger the callback until it returns no cut anymore.
Best regards,
Christian
Dear Christian,
Many thanks for your detailed explanation, and also, I am sorry for my late answer.
I think what you mentioned in the second bullet is very similar to what I am interested in.
Please let me check something, and will get back to you if I have any further questions.
All the best
Abbas
