tkralphs
commented
6 years ago There was indeed an issue, thanks for reporting. It was not really an error in the algorithm per se, but the output was wrong/confusing. I'm still reviewing PR #46, which fixes the problem, to make sure it's the best fix. In the meantime, you can check out the PR if you want and test it yourself. Stay tuned!
We are running the latest version of MibS on Windows 10 to model a bilevel optimization problem in the field of auction design.
It would be great if you could help us with a problem which came up. In our model, lower level variables appear in upper level constraints and an optimal solution of the lower level can create infeasibility in the upper level. We are not sure whether this problem conflicts with the definition of bilevel programs or with the models you allow in your algorithm.
Consider the following model as a simple example: min -x s.t. y <= 0 y \in argmax {y, s.t. y <= 2, y \in R} 5 >= x >= 0; x \in Z
Here, the only solution which fulfills the second constraint (maximizing y with the single constraint y <= 2) is y = 2, which in turn leads to infeasibility in the upper level in combination with the first constraint (y <= 0). Therefore, as we understand it, the full model is infeasible. Of course, we can make the model more sophisticated, allowing for the lower level variable to not appear alone in an upper level constraint. However, using MibS on this model we get a ‘feasible’ solution with x = 5; y = 0:
We are sorry if we are missing something very fundamental here, like that the upper level constraints need to be respected in the lower level program – however to us the definitions did not force this. We would be very grateful if you could help us with this problem. Please find attached the input files we use and the complete log.
Best regards, Richard Littmann
infeasAux.txt
infeasMPS.mps.txt
infeasLog.txt