How to deal with degenerate solutions

[AussiePhysicist]

I've inherited (aka had dumped on me) a complicated but overall fairly simple GAMS model (MIP) looking at market modelling with a number of issues to it. Most of them I can solve (scaling, lack of subsets, multiple other issues) but one that's confounding me a little is that any feasible solution is going to have a large number of degenerate solutions to it.

I've tried to add an insignificant offset to the cause of these to reduce these without perturbing the optimal solution but it hasn't worked. Using CPLEX the solver always identifies several hundred solutions prior to solving (there would be many 1000's) but I'm thinking that this degeneracy makes it take longer than it otherwise should need to. During the solution process it always seems to get to between 5 and 20% relative gap with ~20 solutions and then it stalls, accruing more and more solutions until it eventually and very slowly drops to the pre-set relative gap before polishing a solution.

I've had a quick look at the solution pool options but I'm happy with a single solution, I just want the lowest cost one. Are there any other options I can try, or do I just need to keep trying to break the model degeneracy manually?

[bussieck]

Hi ,not sure I understand everything what you write here. Degeneracy usually means (see https://glossary.informs.org/second.php ... Degeneracy) that we have multiple solution of the same value. You describe that Cplex "always identifies several hundred solutions prior to solving". What means "prior to solving"? Do you mean that in the solution process it finds many incumbents and improves them over time before finding the optimal one. Cplex only reports on new incumbents when there is an improvement, not different incumbents of the same values (unless you use solution pools). The feasible space of a mathematical program often includes a very large number of solutions, but this has nothing to do with degeneracy. That's totally normal and reducing the number of feasible solution does not help the B&C process in a MIP solver. Degeneracy plays little role in MIP (much more in LP). Symmetry in solutions is a much bigger deal for MIPs. Perhaps, you can share your GAMS/Cplex log and point exactly to where you think Cplex "wastes" time.

-Michael

[AussiePhysicist]

Thanks for replying so quickly. Sorry, I was being loose with terminology- when I say degenerate solutions I mean the original person who set this model up has used a bunch of identical options for it to choose from (it's an energy market model and they've used multiple identical gas generators, for example) and so it could select gas_gen1 or gas_gen2, etc, and the outcome would be absolutely identical.

Again, I was being loose with language in that I'm still not across the solver's process, but in the period after its removed the perturbation from the dual objective and is applying cuts, the relative gap reduces and it starts reporting solutions, which I've interpreted, rightly or wrongly, as the model finding solutions with the same objective value. I've taken a quick snippet from an old log file to show what I mean.

If this multiplicity of options isn't an issue I'll be happy, although I want to work on removing it, but if there's anything I can do to aid the solution process I'd love to learn. I've been picking through the CPLEX and GAMS manuals to find things to try.

Thanks again

image.png (10.94 KiB) Viewed 5546 times

[bussieck]

and it starts reporting solutions, which I've interpreted, rightly or wrongly, as the model finding solutions with the same objective value.

This is wrongly assumed. If you would have send the entire width of the log I could have shown you the difference in incumbent values. With what you sent I can only speculate, but basically whenever you see a jump in the gap Cplex found a new and better solution. Even though identical options are not ideal in terms of symmetry, I would assume that Cplex can identify this in presolve. As you probably know MIP has an exponential running time in the worst-case and B&C is in worst-case an exponential algorithm. Often practical models do much better than the theoretical worst-case, but sometimes there is little one can do.

-Michael

[AussiePhysicist]

OK that tells me what I wanted to know then, thanks. Appreciate you taking the time to steer me in the correct direction. I'll worry less about what I thought was a potentially large issue and deal with making the model less clunky.