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).

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).

• GAMSIntroduction.pdf 
  
• AdvancedGAMS.pdf

Microsoft Solver Foundation v1

The Express edition can be downloaded from
http://code.msdn.microsoft.com/solverfoundation/Release/ProjectReleases.aspx?ReleaseId=1799

Start with optimal solution as initial point

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
 

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:

 

(click to enlarge)

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  c9
r1     5   3           7
r2     6           1   9   5
r3         9   8                   6
r4     8               6               3
r5     4           8       3           1
r6     7               2               6
r7         6                   2   8
r8                 4   1   9           5
r9                     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 problem
x.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.

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).

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 solve
with LIMROW set to a large number may produce many
infeasibilities. This script will produce a sorted
list of these infeasibilities so it is easy to find the
largest ones.
 
Erwin Kalvelagen, nov 2005
Updated, 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[2]
 print equation " " arr[2] >> "%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%';
 

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:

Office 2007: Saveas pdf

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

http://www.microsoft.com/downloads/details.aspx?FamilyId=4D951911-3E7E-4AE6-B059-A2E79ED87041&displaylang=en

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

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