CQM solution wrongly flagged as infeasible
I am gearing up to run a couple of benchmarking problems from maritime logistics. The problems exist as MILPs and I just had to write them as CQMs. Before starting these calculations I first tested my code with a tiny test problem: 3 Variables (Real) and 3 constraints. The sampler does in fact find the correct solution to the problem, but flags it as unfeasible, claiming that one of the constraints is broken, even though it is actually not.
Did anyone else encounter this kind of problem and knows how to fix it? It would really be a showstopper for me, because in larger calculations, I will not be able to just look at the result and see, that it in fact is a viable solution, but I will have to rely on the output.
I suspect, that it could be related to the fact that the numbers are real and that the issue is somewhere near numerical accuracy, but at least judging from the numbers, that I can access through the sample_set, I did not find any small deviations from the correct solution.
Comments
Hi Sebastian,
Thank you for using D-Wave Systems. To help us understand the scope of this issue, can you please provide a sample code snippet?
Best Regards,
Tanjid
Hi Tanjid,
thanks for looking into the issue! I can try to work out a minimal code snippet within the next couple of days. If you want, in the meanwhile you can already take a look at the repo itself https://github.com/s-rubbert/MIRP_benchmarking.git specifically: run_optimizations.py. The functions in the beginning are used to parse an MPS file into a CQM. The actual code are lines 143-152.
I split off the part where I actually look at the result into check_out_results.py (to avoid calling the hybrid sampler over and over again).
Best regards,
Sebastian
Hi Tanjid,
thanks again for looking into the problem. It is now solved.
Best regards,
Sebastian
What was the ultimate cause for this and fix?
Hi Bill -
This was an issue with how the files were encoded as input. If you take a look at the commit history on Sebastian's repository linked above, you can see where the fix was made around the date the question was posted.
-Victoria
Thanks Victoria… I was trying to troubleshoot a problem we were having, where we converted an MPS file to LP format using CPLEX and then loaded into CQM only to get infeasible results when classical solvers get feasible ones. So, upon seeing this thread I thought maybe we were seeing something similar. Still testing.
Please sign in to leave a comment.