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

Tuesday, November 11, 2008

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

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:


 

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

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 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%';

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.