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.

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.

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. 

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?

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:

1. Magic squares example.
   
2. User model.

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;

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. 

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.

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.

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:

1. day 1
2. day 2

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.