I am working with a multi-stage mixed-integer stochastic global supply chain optimization problem.
In this regard, under realistic parameter settings, some constraints are making the instances violate the relatively complete recourse assumption. To circumvent the resulting infeasibilities during training, I am enforcing these constraints using binary penalty terms in the objective function.
However, I want to rigorously establish the feasibility of the resulting trained policies. Can I use some statistical test on the binary penalty terms to achieve this? Is it acceptable to use this strategy to establish policy feasibility? If yes, what statistical test should I use?
Infeasibility found in >= 2 stages is common and it is a inherent feature of Benders decomposition. It doesn’t implies the infeasibility of the original compact formulation.
You don’t need to circumvent it, you need to add feasibility cuts.
From my personal experience, dealing with feasibility is more straightforward than resort to penalties. Not only because they obfuscate the problem (making them more complex), but you need to tune more parameters (the penalty coefficient).
If your model does not have relatively complete recourse you likely cannot say anything about the solution.
SDDP.jl does not implement feasibility cuts because, even if we did, we cannot prove that there does not exist some scenario for which the policy is infeasible.
You must (as it seems you have) reformulate your model to have relatively complete recourse.
You can, in simulation, say something about the violations using typical statistics (mean, median, quantile, etc.). You can say something like “We performed 1,000 simulations of the policy, and the penalties are {always zero}/{zero 99% of the time, and the maximum violation is 1e-3}. This gives us confidence that the policy is feasible in practice. However, we cannot discount that there may exist a scenario for which our policy yields an infeasible solution.”
You don’t have to assert that.
If you haven’t been able to experience a scenario for which your first (or the previous) stage decision is infeasible, then maybe you can declare that your current policy is practically feasible.
If you can find a scenario for which your first (or the previous) stage decision is infeasible, then you can attempt to (though you might fail to make sure you can, as it depends on the strength of your cut) generate a feasibility cut to strictly improve your current policy.
This is a philosophical question, not a technical question.
Sure, you can technically add feasibility cuts. And you can generate 10 scenarios and say “see, it’s feasible for all of them! So the expected cost is $57”. But then I can come along with scenario 11 and say “See, your policy yields an infeasible solution!” If the policy is infeasible, is the expected cost $57? No. That’s a meaningless statistic. For all but trivial models, you might sample O(10^3) scenarios. But there might be an infinite number of scenarios (if the policy is cyclic, etc). You only ever get to observe a tiny tiny tiny fraction of the total number of scenarios.
A better way is to create a model with relatively complete recourse from the outset. I have never ever seen a practical model for which this cannot be done. There is always a way to add costly decisions that permit feasibility.
Now, a model with penalties that doesn’t use the penalties in N simulation is exactly the same as a model without penalties that is feasible in the N scenarios. So in one sense you can say similar things about their statistics. But I think it’s important that we ensure users understand that if they have a problem without relatively complete recourse they cannot claim to have found a feasible policy.
But if we sample scenarios during evaluation phase statistically significant times and then come up with the results from which we can infer with 0.95 confidence level that the policy will be feasible in the whole population of scenarios, will it be appropriate scientifically within the operations research community?
In my model, I can claim that if the constraints (which are creating RCR violations) are violated then fines will be incurred or an expensive (extended) capacity is borrowed but this will make me to create similar variables and penalties in other places (in the model) where RCR violations are not happening (with realistic parameter settings), consequently increasing the complexity of an already complex model.
Let’s change the situation. Assume I have a large linear program. I have a solution vector x. I couldn’t be bothered checking that all the constraints hold, but I randomly sampled 100 of them and they seemed okay so I declare that my solution is probably feasible. Would you ever write that in a paper?
As I said above, this is a philosophical question. Not a technical one. You can come up with a variety of statistical arguments. My position is that they are misleading. If you do not have relatively complete recourse then you cannot claim to have found a feasible policy, and therefore you cannot claim to have solved the model.
I think you are right and therefore it will be correct to reformulate the model by adding a reformulation section in which I add the provision of penalties in case of the breach of contract enforced by certain constraints creating RCR related issues.
In case of other constraints creating similar issues I have decided to add the provision of bowering of extended capacities at facilities (hubs) in my model.
Yes, Lagrangian cuts can withstand mixed-integer circumstances (optimality or feasibility).
Nonetheless, it highly depends on your problem formulation, therefore abundant nontrivial issues exist. It is not as easy as Benders’ cuts (optimality or feasibility) in the continuous setting.