topic Re: Optmodel speed in Mathematical Optimization, Discrete-Event Simulation, and OR

Optmodel speed

cloudyhill — Mon, 07 Dec 2015 19:39:34 GMT

I have a MILP problem to solve in SAS optmodel. After presolve, it has 500 variables, 1000 constraints, 18000 non-zero coefficients. Out of the 500 variables, most of them are binary, a few are integer and non-integer. I don't think this is a big problem but it's taking more than hours to solve. I wonder why this is so? Memory issue? I run the code in EG and a remote server.

I used

solve with milp/nodesel=1 inttol=1e-8;

Because nodesel slightly speed up a little on smaller problems, and I need the integer to be very accurate.

Re: Optmodel speed

LeoLopes — Tue, 08 Dec 2015 03:51:32 GMT

Your problem is not large. Size is important, but it is not the most useful predictor of MILP running time. If your problem is related to an NP-Hard problem, it will tend to be hard to solve even if it is easy to write the model down as a MILP, and even the problem instance is small.

There are formulation approaches and manipulations of the instance that you can encode in OPTMODEL that help. It is impossible to dispense advice regarding what to try without more information about the model.

You might be able to leave inttol at its default value. Round the solution after the solve with the default inttol, and check if it is feasible. There are important but rare cases where this fails, which is why the solver doesn't simply round the solution for you. Leaving the parameter at the default value might help with speed.

Re: Optmodel speed

cloudyhill — Tue, 08 Dec 2015 22:10:03 GMT

Thanks for your advice. I tried removing inttol, but it still hasn't solved the problem after 8 hours. The other run with inttol=1e-8 hasn't solved after 24 hours. Then I moved the model from SAS to CPLEX with some grammar change, no formulation change. CPLEX solved in 8 seconds.

What I am doing is building an optimization model for a bidding system with quite complicated bidding rules. To test the model in SAS, I randomly generated a few test sets. Sometimes SAS takes 20~40 minutes to solve examples with 40 biddders. But for this example, there are 35 bidders, but just can't be solved in a reasonable time.

Re: Optmodel speed

LeoLopes — Wed, 09 Dec 2015 01:00:23 GMT

It is not unusual to encounter large differences in performance between different solvers. BTW, it also happens the other way. Modern solvers are sophisticated collections of algorithms. The order in which each solver applies those algorithms determines the success they will have on each instance. As you have observed, even within the same problem, a slightly different instance can cause the solver to take a different, less favorable search path. We tune solvers against a large set of customer instances and academic instances at each release. I am sorry that your instance was on the unluckly side.

If you are able to share your model and instance generator with us, that could help us service you better in future releases. This code will never be shared with any other customer.

If you are unable to share your model, we can still help you: please send us the instance that had the greatest relative performance difference to CPLEX using the OPTMODEL 'SAVE MPS' statement. That protects your model, and might still help us find out if there is something we can do differently.

If you are able to help, please create a support entry. Unfortunately, I cannot promise to tune the solver for your specific model. But I can promise to route your support ticket to our developers, which will help us increase performance in future releases.

Thanks in advance!

Re: Optmodel speed

cloudyhill — Mon, 04 Jan 2016 20:09:24 GMT

Hello Leo. I'd love to work with SAS on this case. I was finally able to submit a support entry. Thank you so much for your suggestion!

Re: Optmodel speed

LeoLopes — Tue, 05 Jan 2016 00:20:15 GMT

That's great! We really appreciate your effort in sharing the instance with us. I sent an email to the contact in the track. If you can, please confirm that I have the right track, and I'll forward it to the right people.

Thanks again!

Leo.