## Wednesday, November 19, 2008

### MS Solver Foundation: Excel/OML issue

I was sometimes loosing the model information when exiting Excel. Turns out that when you save the spreadsheet after closing it (Excel will prompt you if you want to save your changes) the OML model gets lost. (Somewhat a warped way of saving the workbook, but that is how my brain is wired.) If you manually save the model before closing Excel, the model will be saved without a problem. Microsoft could reproduce it and it is quickly fixed in the next version. (See issue report).

I had hoped to solve the assignment problem suggested by Knuth. It is supposed to find "interesting" spots on the Mona Lisa. Unfortunately, the standard edition of MS Solver Foundation is "throttled" too tightly to be able to solve this large but easy model. I am sure this is not a good business case to purchase the Enterprise version! (See limits).

## Sunday, November 16, 2008

### Powerpoint of GAMS presentations

Below are some of the powerpoint presentations on a GAMS workshop taught at Univ of Tennessee (the sheets of the presentation on some UTK application specific issues are not repreduced).

## Friday, November 14, 2008

### Microsoft Solver Foundation v1

http://code.msdn.microsoft.com/solverfoundation/Release/ProjectReleases.aspx?ReleaseId=1799

## Tuesday, November 11, 2008

Large NLP's are difficult, not in the least because the chance increases that numerics become more unstable. Here is an example of such a problem with a square system (having 224k equations and variables):

``solve m minimizing dummy using nlp;x.fx(ivar,t) = x.l(ivar,t);solve m minimizing dummy using nlp;``

We fix the variables to their optimal values and solve again. This gives for the second solve:
``               S O L V E      S U M M A R Y      MODEL   m                   OBJECTIVE  dummy     TYPE    NLP                 DIRECTION  MINIMIZE     SOLVER  CONOPT              FROM LINE  554557 **** SOLVER STATUS     1 NORMAL COMPLETION         **** MODEL STATUS      4 INFEASIBLE                **** OBJECTIVE VALUE                0.0000 ``

We get some good advice how to work around this by loosening some tolerance:
`` ** An equation is inconsistent with other equations in the    pre-triangular part of the model.      Residual=           3.78931873E-08    Tolerance (Rtnwtr)= 2.00000000E-08      The pre-triangular feasibility tolerance may be relaxed with    option:      Rtnwtr=x.xx      E_CRIMSONSTEOQEN(2017): Inconsistency in pre-triangular part of model.     The solution order of the critical equations and    variables is:     All variables in equation E_CRIMSONSTEOQEN(2017) are now fixed    and the equation is infeasible. Residual =-3.7893187255E-08 ``

## Monday, November 10, 2008

### Sudoku: Constraint Programming vs MIP

The Sudoku puzzle can be coded easily using constraint programming thanks to built-in constructs that handle the all-different constraint. Here is an example using the Microsoft Solver Foundation CSP solver:

The only difficulty was to model: for all i,j such that d[i,j]>0 require that x[i,j]=d[i,j]. I used the following formulation: Foreach[{i,I},{j,J},x[i,j]==d[i,j] | d[i,j]==0] where | is an "or" operator.

The complete model looks like:
``Model[   Parameters[Sets,I,J],  Parameters[Integers,d[I,J]],   Decisions[Integers[1,9],x[I,J]],   Constraints[     // Alternative 1: (does not work in the beta)    //FilteredForeach[{i,I},{j,J},d[i,j]>0,x[i,j]==d[i,j]],    // Alternative 2:     Foreach[{i,I},{j,J},x[i,j]==d[i,j] | d[i,j]==0],     Foreach[{i,I},Unequal[Foreach[{j,J},x[i,j]]]],    Foreach[{j,J},Unequal[Foreach[{i,I},x[i,j]]]],      Foreach[{ib,3},        Foreach[{jb,3},            Unequal[Foreach[{i,ib*3,ib*3+3},{j,jb*3,jb*3+3},x[i,j]]]         ]    ]  ] ]``

The above sudoku can also be coded in GAMS:

``\$ontext  Sudoku solver  September 2005   Code written by:     Paul van der Eijk     GAMS Development Corporation     1217 Potomac Street NW     Washington DC, 20007     Tel: (202) 342-0180 Fax: (202) 342-0181     Email: paul@gams.com     WWW: http://www.gams.com   Based on Latin Square example in GAMS model library.   Adapted to solve a Sudoku problem by:     Sherman Robinson     Economics Department     University of Sussex     Brighton BN1 9SN     UK     email: sherman.robinson@sussex.ac.uk  \$offtext sets r  rows    / r1 * r9/ c  columns / c1 * c9/ v  values  / v1 * v9/ sc sub-col /sc1 * sc3/ sr sub-row /sr1 * sr3/ scs(sc, c) /sc1.(c1*c3), sc2.(c4*c6), sc3.(c7*c9)/ srs(sr, r) /sr1.(r1*r3), sr2.(r4*r6), sr3.(r7*r9)/; table problem(r,c)      c1  c2  c3  c4  c5  c6  c7  c8  c9r1     5   3           7r2     6           1   9   5r3         9   8                   6r4     8               6               3r5     4           8       3           1r6     7               2               6r7         6                   2   8r8                 4   1   9           5r9                     8           7   9;display problem; Parameter  value(v) "Values";value(v) = ord(v) ; binary variable x(r,c,v);variable w;equations  eq1(r,c)        "exactly one value for each cell"  eq2(c, v)       "columns entries have to be unique"  eq3(r, v)       "row entries have to be unique"  eq4(sr, sc, v)  "sub-squares have to be unique"  nobj            "definition of objective - anything"; eq1(r, c)..   sum(v, x(r, c, v)) =E= 1;eq2(c, v)..   sum(r, x(r, c, v)) =E= 1;eq3(r, v)..   sum(c, x(r, c, v)) =E= 1;eq4(sr, sc, v).. sum((c,r)\$(scs(sc, c) and srs(sr, r)), x(r, c, v)) =E= 1; nobj..      w =E= sum((r, c, v), x(r, c, v)); *SR Fix values in the problemx.l(r,c,v)\$(problem(r,c) = value(v)) = 1 ;x.fx(r,c,v)\$(x.l(r,c,v) = 1)         = 1 ; option limrow=1000, limcol=0;option mip=cplex;model sudoku /eq1, eq2, eq3, eq4, nobj/;solve sudoku minimizing w using mip; parameter  solution(r,c)   "Display of results";loop(v,  solution(r, c)\$(x.l(r, c, v)) = Ord(v););option solution:0:1:1;display solution;``

I wrote an Excel based GUI for this model as an example, see http://www.amsterdamoptimization.com/packaging.html.

## Friday, November 7, 2008

### Delphi Usenet Groups

are no longer the place to be. Go instead to: https://forums.codegear.com/

The best one is of course Delphi Non-technical: https://forums.codegear.com/forum.jspa?forumID=67 (see how developers digest the new unicode strings or complain about the help functionality).

## Thursday, November 6, 2008

### Infeasible initial point: reporting

This model parses a listing file and produces a sorted list of the infeasibilities of the initial point. Note that you need to set OPTION LIMROW to a large number for this to work.

No need to set LIMCOL: all variables are always feasible.

``\$ontext If a calibration is not correct, the benchmark solvewith LIMROW set to a large number may produce manyinfeasibilities. This script will produce a sortedlist of these infeasibilities so it is easy to find thelargest ones. Erwin Kalvelagen, nov 2005Updated, oct 2007 \$offtext \$set LISTING china.lst\$set UNSORTED unsorted.txt\$set SORTED sorted.txt\$set SCRIPT infes.awk  \$onecho > %SCRIPT% /^Equation\ Listing/ { eqlisting=1} /^.*\.\./ { if (eqlisting==1) {    equation = \$1    gsub(/\./,"",equation) }} /INFES\ =\ [0-9A-Z.]*\ \*\*\*/ { if (eqlisting==0) {   next }  match(\$0,"(INFES = )([0-9A-Z.]*)",arr) print equation " " arr print equation " " arr >> "%UNSORTED%"}  /^Model Statistics/ { exit}  \$offecho execute '=rm -f %UNSORTED%';execute '=rm -f %SORTED%';execute '=awk -f %SCRIPT% %LISTING%';execute '=gsort -n -k 2 -r -o %SORTED% %UNSORTED%';execute 'echo inspect %SORTED%'; ``

## Wednesday, November 5, 2008

### Microsoft Solver Foundation: OML

I have now been playing a bit with the Microsoft Modeling Language. It is really amazingly simple, and the integration with Excel is very interesting.

Of course we miss a number of things like data manipulation, loops, checks etc.  Also there are still a few bugs, but this is a beta. Some syntax is somewhat surprising. E.g. {i,1,4} means i=1,2,3. It is better to make all arrays zero based. In that case one can use e.g. Sum[{i,N},x[i]] as the default lower limit in a sum is zero (i.e. {i,N} is the same as {i,0,N}, or i=0,..,N-1).

The next screen shot illustrates all these points. With a little UI:

## Saturday, November 1, 2008

### Office 2007: Saveas pdf

There is an Office add-in that allows to save documents as PDF files:

Another tool is CutePDF from http://www.cutepdf.com

The Microsoft utility gives better pdf rendering in documents where I have embedded screenshots.