Obsidian | Level 7

optmodel efficiency

Hi,

Up to now I was using MS Excel's solver for solving optimisation problems. I decided to switch to SAS in order to get a real boost in optimisation speed.

To my surprise my optimisation problem is solved by Excel's solver in 5 seconds, while SAS needs at least 2 minutes for the same problem. It's really odd - any suggestions why there's such irrational difference in speed? Seems impossible. I tried all quadratic OPTMODEL methods and 2 minutes is the best result.

1 ACCEPTED SOLUTION

Accepted Solutions
SAS Super FREQ

Re: optmodel efficiency

var r {i in VSET};

con rc {i in VSET}: r = sum {j in WSET} values[i,j] * weights - margins;

var avg;

con avgc: avg = sum {k in VSET} r / NOBS;

By the way, to invoke the QP solver, you should explicitly specify

solve with QP;

solve;

I realize my tom022012_heur.sas code had just SOLVE, but SOLVE WITH QP is more efficient since otherwise you get the default NLP solver instead of the more specialized QP solver.

And be sure to drop the rc and avgc constraints  if want to then solve the subsequent MILP.

This takes only a few seconds to solve with 20000 observations in 9.2 on my machine.  But I'm a bit confused about your run times---how did you run this without impvar and without correct var/con replacement?  Can you please post the code you ran?

11 REPLIES 11
SAS Super FREQ

Re: optmodel efficiency

Can you please provide your data and code?  Also, what version of SAS are you running?

Obsidian | Level 7

Re: optmodel efficiency

SAS 9.2. The problem is the same as one in answer 9. - the code with heuristic approach:

In that example there were only 3 observations. I need to perform optimization on at least 20000 many times so I was expecting that SAS can make one optimisation much quicker than Excel's solver.

When I try with 1000 observations SAS with heuristic approach needs 54 seconds to optimize while Excel's solver with 10.000 oservations (10x more) needs 5 second. I don't know why the difference is so huge.

SAS Super FREQ

Re: optmodel efficiency

Please provide your input data with 1000 observations, and I will take a look.

Obsidian | Level 7

Re: optmodel efficiency

1) I attached zipped files with over 67000 observations. I need to make optimization on around 20.000 observations.

2) I use SAS 9.2 so I can't use impvar declarations which, if I undestood well, significantly increase speed of optimization.

I tried to substitute them with var and con declarations but I get error:

 impvar r {i in VSET} = (sum {j in WSET} values[i,j] * weights) - margins;

impvar avg = (sum {k in VSET} r) / NOBS;

min min_std = sum {i in VSET} (r - avg)**2;

num std = sqrt(min_std.sol / NOBS);

My try to replace them:

var r {i in VSET}; con rc {i in VSET} = sum {j in WSET} values[i,j] * weights - margins;

var avg; con avgc = sum {k in VSET} r / NOBS;

min min_std = sum {i in VSET} (r - avg)**2;

num std = sqrt(min_std.sol / NOBS);

How should I change them to work on SAS 9.2?

SAS Super FREQ

Re: optmodel efficiency

var r {i in VSET};

con rc {i in VSET}: r = sum {j in WSET} values[i,j] * weights - margins;

var avg;

con avgc: avg = sum {k in VSET} r / NOBS;

By the way, to invoke the QP solver, you should explicitly specify

solve with QP;

solve;

I realize my tom022012_heur.sas code had just SOLVE, but SOLVE WITH QP is more efficient since otherwise you get the default NLP solver instead of the more specialized QP solver.

And be sure to drop the rc and avgc constraints  if want to then solve the subsequent MILP.

This takes only a few seconds to solve with 20000 observations in 9.2 on my machine.  But I'm a bit confused about your run times---how did you run this without impvar and without correct var/con replacement?  Can you please post the code you ran?

Obsidian | Level 7

Re: optmodel efficiency

Thank you for help. Coming back to discussion:

1) Almost at the same time I started to try enforce different solvers and figured out also that QP is the quickest. I'ts good that you recommend QP - I wasn't sure If I can trust QP beacuse it has "experimental" label. Thank you

2) After adding proper constraints istead of impvar my calculation times dropped to 10 sec with 10.000 obs. and seem to grow linearly (in comparison to expotential growth without QP solver and proper constrainsts). Now the times are really ok to me - however further speed up is important to me as I may have to make such optimizations many times (100, 1000) depending on scenario defined.

3) Can you explain why I should make sure to drop rc and avgc constraints before solving MILP?. I thought that I should solve normal QP problem as quick as possible and then find solutions that meet discrete criteria most close to my optimal solution (solved in step one)?

4) You mentioned somewhere that OPTMODEL in SAS 9.3 is much quicker than in SAS 9.22 . Does it apply to SAS 9.22 too? Can you roughly estimate how quicker can it be with my problem on the same configuration?

5) One thing I did not realised could be an issue here too:

Apart from minimization of standard deviation I need to maximize also Average/standard deviation ratio. I thought that I will use the same solver in this case too but QP solver says that It needs quadratic objective and can't solve it. How can I formulate such objective in order to use QP solver or other solver to get reasonably quick result?

6) When I try to solve Average/standard deviation ratio problem with just SOLVE then I constantly get out of memory error saying that SAS needs 295 MBytes of memory :

(ERROR: Unable to allocate sufficient memory. At least 294925K bytes were requested. You must

either increase the amount of memory available, or approach the problem differently)

First af all SAS has much memory available more for the problem. Secondly I tried to put various statements in SAS cfg file (-MEMSIZE 0, -MEMSIZE MAX , -LOADMEMSIZE 0 etc.) without success. Can you help me with setting sas not to run out of memory possibly ever - my scripts will be run hundreds of times so I prefer to get results even later to getting just an error.

By the way - on SAS startu I get message in log:

 Memory 3908k OS Memory 4976k

Does SAS mean megabytes instead of kilobytes or these are kilobytes and it is a real cause of my memory problems? I have 3GB of RAM.

SAS Super FREQ

Re: optmodel efficiency

1. The QP solver is production in 9.3, so that is another reason to upgrade.

2. I am still not sure what you were running before, but I'm glad to see that you are getting run times in seconds now.

3. It is OK not to drop the rc and avgc constraints when solving the MILP, but keeping them unduly stresses the MILP presolver.  The QP step finds  an optimal continuous solution.  The MILP step finds the closest integer solution to that QP solution and doesn't need to know that the first solution came from the QP solver.  If you drop the constraints, you will need to recompute the std after the MILP solve.  If you use IMPVAR instead, this computation is automatically computed for you.

4. On my machine, I see about a 2-fold speedup between 9.2 and 9.22.  I get another 2-fold speedup from using IMPVAR, for a 4-fold speedup in total.

5. If you change the objective from quadratic to something non-quadratic nonlinear, then you need to use one of the NLP solvers.

6. The default MEMSIZE is typically too small for optimization problems.  You can set it explicitly, as described here:

http://support.sas.com/documentation/cdl/en/ormpug/63975/HTML/default/viewer.htm#ormpug_optmodel_sec...

By the way, some of your observations have missing values.  I replaced them with 0 to avoid errors, but you probably want to do something else.

Obsidian | Level 7

Re: optmodel efficiency

2. I was running codes that you posted https://communities.sas.com/servlet/JiveServlet/download/116717-11110/tom022012_heur.sas.zip and https://communities.sas.com/servlet/JiveServlet/download/116717-11111/tom022012.sas.zip but slightly modified - I just removed impvar statements that caused errors in sas 9.2 and included parts of that codes in objective function. Now I know that impvar statements should be replaced with var and con statements and properly formulated quadratic function with QP solver works effectively.

3. Ok, now I understand. You mean to use drop statement after QP solver and before MILP solver not removing constraints form the whole code. Right?

4. Good to know.

5. I seem to have still problem here. When I changed objective to non quadratic one I cannot solve problem even with 1000 observations in less than 10 minutes (300 obs - 2 seconds, 500 - 10 seconds, 1000 -10minutes). The time needed increases expotentially and since I need to solve problem with 10.000 or more observations it becomes unsolvable for me. Morover I run out of memory with 2000 observations.

What are solving times on you computer when you change solver to eg. NLPC and change objective to : max max_shp = a / (sqrt(sum {i in VSET} (r - a)**2)/NOBS);    (AVERAGE/STDEV)

6. Is there a possibility to enforce SAS to use some disk space so that the solver wouldn't run out of memory? I need to make code that always works - even if the problem is too complicated and lasts long.

SAS Super FREQ

Re: optmodel efficiency

3. Right

5. I tried your new objective with 10000 observations.  With explicit var/con, runs out of memory.  With IMPVAR, solves in one second.

6. There is currently no such feature, although that idea is a possibility for a future release.  But if you use IMPVAR, your problem has only 10 variables and 1 constraint, so it shouldn't be an issue.

Obsidian | Level 7

Re: optmodel efficiency

5. So summing up : without SAS 9.22 or 9.3 and IMPVAR statement I won't be able to solve it in short time?

Is there any reason why Excel solves it in 2-3 seconds? I found that Excel Solver uses  Generalized Reduced Gradient Algorithm http://support.microsoft.com/kb/82890 ( Solver Uses Generalized Reduced Gradient Algorithm) . Is there a possibility to use the same algorithm in optmodel and get results in seconds without running out of memory?

SAS Super FREQ

Re: optmodel efficiency

Yes, the use of IMPVAR seems critical for your problem.  I'm not familiar with the internals of Excel Solver or that algorithm.  You could certainly implement it yourself by using the programming language features of OPTMODEL.  But I would recommend upgrading to 9.3 instead.

Discussion stats
• 11 replies
• 2427 views
• 3 likes
• 2 in conversation