Wednesday, December 31, 2008

GAMS/Cplex out-of-memory issue

This model runs out of memory in the branch-and-bound.

Elapsed real time = 15952.23 sec. (tree size = 1929.62 MB, solutions = 5)
Nodefile size = 1802.18 MB (732.60 MB after compression)
2237100 2069567 2.0773 84 2.1636 2.0742 53354065 4.13%
2237200 2069665 2.0742 86 2.1636 2.0742 53356034 4.13%
2237300 2069763 2.0773 87 2.1636 2.0742 53358318 4.13%
2237400 2069857 2.0758 84 2.1636 2.0742 53360030 4.13%
2237500 2069955 2.0758 84 2.1636 2.0742 53362567 4.13%
2237600 2070055 2.0742 86 2.1636 2.0742 53364576 4.13%

Warning: MIP starts not constructed because of out-of-memory status.

Consider using CPLEX node files to reduce memory usage.
CPLEX Error 1001: Out of memory.


It would be useful if this case would be handled more gracefully. Now it just stops and no solution is returned:

**** SOLVER STATUS     4 TERMINATED BY SOLVER
**** MODEL STATUS 14 NO SOLUTION RETURNED
**** OBJECTIVE VALUE 0.0000

RESOURCE USAGE, LIMIT 15955.664 21600.000
ITERATION COUNT, LIMIT 0 10000


It should be possible to allocate memory before starting the branch-and-bound so that always the best integer solution so far can be reported. Note also that the iteration count reported is wrong.

Monday, December 29, 2008

Another difficult MIP

Some MIP models are small but very difficult. An example is described here (this model has 252 binary variables). Now I am working on a very small scheduling application with only 217 binary variables. Cplex finds good solutions very quickly, but it is not able to close the gap in any significant way in 6 hours.

Some fragments of the log:


Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap

* 0+ 0 16.1636 0 ---
0 0 0.1000 195 16.1636 0.1000 1406 99.38%
* 0+ 0 14.1636 0.1000 1406 99.29%
0 0 0.1000 189 14.1636 Fract: 5 2050 99.29%
* 0+ 0 13.1636 0.1000 2050 99.24%
0 2 0.1000 189 13.1636 0.1000 2050 99.24%
* 10+ 4 3.1636 0.1000 14281 96.84%
* 40+ 32 2.1636 0.1000 42176 95.38%
100 94 1.3142 63 2.1636 0.1000 86823 95.38%
200 171 0.3685 127 2.1636 0.1000 129897 95.38%
300 259 0.3646 109 2.1636 0.1000 187075 95.38%
400 346 0.2071 106 2.1636 0.1000 228382 95.38%
500 428 0.1500 118 2.1636 0.1000 266899 95.38%
600 167 1.3995 65 2.1636 0.1000 331430 95.38%
700 208 2.1535 46 2.1636 0.1000 378191 95.38%
800 247 0.8702 74 2.1636 0.1000 443716 95.38%
900 323 0.1286 135 2.1636 0.1000 482839 95.38%
1000 409 1.4927 48 2.1636 0.1000 518560 95.38%
Elapsed real time = 399.27 sec. (tree size = 0.39 MB, solutions = 5)
.....
61100 52481 1.1364 98 2.1636 0.1358 30494218 93.72%
61200 52569 1.2453 56 2.1636 0.1359 30547758 93.72%
61300 52657 0.9057 121 2.1636 0.1360 30590947 93.71%
61400 52749 0.7052 114 2.1636 0.1361 30643445 93.71%
61500 52837 2.1447 58 2.1636 0.1364 30695673 93.70%
61600 52921 0.8114 105 2.1636 0.1364 30735655 93.70%
61700 53005 2.1333 89 2.1636 0.1364 30790214 93.70%
61800 53087 cutoff 2.1636 0.1364 30824849 93.70%
61900 53174 0.1500 118 2.1636 0.1364 30878206 93.70%
62000 53262 0.6538 111 2.1636 0.1364 30942477 93.70%
Elapsed real time = 21434.12 sec. (tree size = 51.02 MB, solutions = 7)
62100 53348 1.1516 75 2.1636 0.1364 31008777 93.70%
62200 53434 1.1409 113 2.1636 0.1364 31064891 93.70%
62300 53527 1.2003 90 2.1636 0.1364 31107576 93.70%
62400 53610 0.9534 91 2.1636 0.1364 31154949 93.70%
62500 53696 cutoff 2.1636 0.1364 31192217 93.70%
...
Resource limit exceeded.

MIP Solution: 2.163636 (31215703 iterations, 62517 nodes)
Final Solve: 2.163636 (0 iterations)

Best possible: 0.136364
Absolute gap: 2.027273
Relative gap: 0.936975


An integer solution with obj=2.1636 is quickly found. Two other integer solutions are found down the road, but they don't improve on this significantly. The best relaxation bound is moving very slowly, and as a result the closing of the gap is sluggish.

Wednesday, December 17, 2008

Mona Lisa assignment in GAMS

This is the assignment problem described in Donald E. Knuth, "The Stanford GraphBase: A Platform for Combinatorial Computing", ACM Press, 1993. The gray scale data was generated by lisa(360,250,255,0,360,0,250,0,22950000) and is used to color (small) Excel cells.

The GAMS model is as follows:


$ontext

Assignment problem for lisa(360,250,255,0,360,0,250,0,22950000)

Erwin Kalvelagen, March 2002

Reference: Donald E. Knuth, "The Stanford GraphBase:
A Platform for Combinatorial Computing", ACM Press, 1993.


$offtext


set i 'rows' /0*359/;
set j 'columns' /0*249/;

$if exist input.gdx $call 'rm -f input.gdx'
$if exist output.xls $call 'rm -f output.xls'


$call '=gdxxrw.exe i=input.xls par=c rng=Data!A1 rdim=1 cdim=1'

parameter c(i,j);
$gdxin input.gdx
$load c

equations
objective 'maximize highlighted parts'
column(j) 'column sum'
row(i) 'row sum'
;

variables
z 'objective variable'
x(i,j) 'pixels'
;

binary variable x;

objective.. z =e= sum((i,j),c(i,j)*x(i,j));
row(i).. sum(j, x(i,j)) =l= 1;
column(j).. sum(i, x(i,j)) =e= 1;

model m /all/;
solve m using rmip maximizing z;

set solution(i,j);
solution(i,j)$(x.l(i,j)>0.5) = yes;
execute_unload 'output.gdx',solution;

execute '=gdxxrw.exe i=output.gdx o=output.xls set=solution rng=Solution!A1 rdim=2 cdim=0'



This model is stored inside the Excel spreadsheet. The Excel front-end will export the model and the input data to a temp directory. Then GAMS is called, and finally the resulting solution data is read. To make it possible to use gdxxrw inside the GAMS model, we use the following algorithm:

  1. Write GAMS model to %TEMP%\MonaLisa.gms
  2. Write Data sheet to %TEMP%\input.xls
  3. Call gams to execute %TEMP%\MonaLisa.gms
  4. Copy %TEMP%\output.xls to Solution sheet
  5. Draw points in Solution sheet with different color
Note that GDXXRW cannot read/write directly to the spreadsheet that has VBA code running, neither can we make it shareable. This algorithm bypasses this problem by copying input and output data to external workbooks.


The model is a large but easy RMIP: 600 equations and 90,000 variables. The free LP solver CBC can solve this quickly: 0.6 seconds. Note: the model is too large to solve with MS Solver Foundation Express and Standard Editions (see: note). Using the Check button in the MS Solver Foundation Excel plug-in seems to indicate that the Excel binding is somewhat slow. In addition the plug-in does not provide a progress window (see second picture below) which is very useful for long running MIP models. Although the GAMS/EXCEL/VBA route requires more programming, for some classes of models this approach seems more flexible than the MS Solver Foundation Excel plug-in solution. Of course for ultimate flexibility at the cost of even more programming effort you can use the MS Solver Foundation .NET API's.











Coin OR's CBC performance

COIN OR's CBC solver is often showing excellent performance. Here is an example of a somewhat difficult MIP:
  • LP solve: 4 hours (as reported by user)
  • Cplex: 135 seconds 
  • CBC: 183 seconds
(all using defaults). 

If you have the funds to buy Cplex: running Cplex on 4 cores and more aggressive cut generation reduced the solution time to 33 seconds. 

Sunday, December 14, 2008

Max Water Retaining Magic Squares

This is new to me: http://www.knechtmagicsquare.paulscomputing.com/topographical.html.

Is there more information on this? Can this formulated as a MIP or CSP model?

Thursday, December 11, 2008

MSF CSP: Domain Over Weighted Degree

The setting Domain Over Weighted Degree seems to be useful for a number of CSP models in the Microsoft Solver Foundation. 

Examples:

GAMS $macro

GAMS 22.9 has some macro facilities. I don't completely understand it. The following model:

$macro a b
scalar a/1/;
display a;

gives:
   1  $macro a b
2 scalar a/1/;
**** $195,409
**** 195 Symbol redefined with a different type
**** 409 Unrecognizable item - skip to find a new statement
**** looking for a ';' or a key word to get started again
3 display b;
**** $140
**** 140 Unknown symbol

**** 3 ERROR(S) 0 WARNING(S)
Apparently it is skipping some substitutions. This is not like what I am used to in macro preprocessors for languages like C and Delphi.

I would expect this model to behave like:
scalar b/1/;
display b;

Tuesday, December 9, 2008

How to generate a PNG/GIF file with multiple plots?

Gnuplot allows to generate bitmaps containing multiple plots. See below. The code can be found in rabbitplot.gms. If you want to do more with Gnuplot you may want to keep an eye on this upcoming book.


MSFCli.exe

Some issues I raised wrt MSFCLi.exe will be fixed in the next release of MS Solver Foundation.

Wrapper around INVERT.EXE

Bruce McCarl built some wrapper around INVERT.

Rebuttal: I have used this tool for many years in many different projects without ever having the need to invert a square matrix over different sets. I would conjecture that the model is in all likelihood incorrectly organized if you need such functionality. Besides, it was my thought that if needed I can always use a simple mapping to overcome this limitation (again: I never had to do this). But of course it is an excellent idea to extend the functionality of INVERT using the proposed wrapper.

Solution of large NLP model with Mosek

This report shows some good results with Mosek on a very large convex NLP model. 

Monday, December 8, 2008

LS advert in mccarl guide

3.4.3.3.27 LS

LS is a solver for estimating linear regression models in GAMS. It solves the normal equations (X'X)b=X'y to introduce numerical instability. It was originally developed by Erwin Kalvelagen is the original author [sic] and further information can be found in the solver manual or at the Amsterdam Optimization Modeling Group's web site.

This statement is not completely correct. I surely don't want to solve the normal equations to introduce numerical instability. Actually I don't form the normal equations at all (for good reasons). The algorithm is based on a stable QR decomposition (see section 5 of LS solver documentation). The code has been verified to solve some very numerically challenging problems. Some users have used LS to solve regression problems with hundreds of coefficients to estimate.


Sunday, December 7, 2008

How to express a normal distribution function in GAMS.

> How can I express a Normal distribution function (CDF)
> in GAMS?

errorf((X-mu)/sigma)

See also: http://amsterdamoptimization.com/pdf/specfun.pdf for more information.

Saturday, December 6, 2008

Redeclarations in GAMS

> Erwin:
> To my surprise GAMS allows
> variable x,x;
> Any reason for this?

GAMS allows redeclarations of symbols unless there is a contradiction. I.e. one often sees:

variable x(i),y,z;
positive variable x;

This is perfectly legal GAMS. Not allowed is:

positive variable x;
negative variable x;

Your example is allowed as there is no contradiction. 



GAMS/GDX workshop at USDA/ERS

I have been busy these weeks. Taught a GAMS/GDX workshop at USDA/ERS:

Invited Talk at "Scheduling in the Process Industry", Bad Honnef

Urged by Josef Kallrath, I presented at the meeting Scheduling in the Process Industry this talk.

This was a great venue.