Wednesday, November 30, 2011

MPS files: this does not look right

Writing an MPS for a QP model from GAMS using the Cplex option writemps I saw this:

* ENCODING=ISO-8859-1
NAME          gamsmodel
ROWS
obj
obj
E  budget
G  retcon
COLUMNS
    z         obj                             1
    z         obj                             1
    x(GAB)    budget                          1
    x(GAB)    retcon                     0.0025
    x(GAP)    budget                          1
    x(GAP)    retcon                     0.1375

This does not look right. Probably a problem in the GAMS link where a new free row is added to the problem with the same name as an existing row.

Wednesday, November 23, 2011

This does not compute

GLPK doesn't accept an constraint in which a variable is devided by an variable, i would like to know if there is some solution to linearize this constraint. knowning that var2 is binary and var 1 is reel in case var1 / var 2.

This means var2=1 and we can replace the expression var1/var2 by var1.

Recently read

During a transatlantic flight I had the opportunity to read this book on parallel programming for .Net. It describes some of the higher level constructs available in .Net that make it easier to implement parallel algorithms. Of course the big issue is that you need to (re)design your algorithms to make parallel operations effective or even possible. Some algorithms are just not very amenable to be parallelized (the Simplex method for LP being a good example). The book contains enough warnings to make you think twice before starting to work on parallel implementations.

Monday, November 21, 2011

MPS Files (2)

As follow up on http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/mps-files.html it is noted that Microsoft Solver Foundation also reads some MPS files incorrectly. E.g. consider the files:

C:\Users\erwin\Documents>type mip4mps.oml
Model[
  Decisions[Integers[0, Infinity], x],
  Constraints[x <= 5],
  Goals[Maximize[x]]
]

C:\Users\erwin\Documents>type output.mps
NAME          MODEL
ROWS
L  constrai
N  goal_8ef
COLUMNS
    INTMARK   'MARKER'                 'INTORG'
    x         constrai   1             goal_8ef  -1
    INTMARK   'MARKER'                 'INTEND'
RHS
    RHS       constrai   5
BOUNDS
ENDATA

C:\Users\erwin\Documents>

The MPS file was generated from the OML file. If we inspect the MPS file we see no bounds on x. This means the variable x should be binary.

If we solve the MPS file with Solver Foundation we see:

C:\Users\erwin\Documents>"\Program Files (x86)\Microsoft Solver Foundation\3.0.2.10889\Bin\MSFCli.exe" +verbose 3 output.mps
===== Processing .\output.mps =====
Solution Quality: Optimal
===Solver Foundation Service Report===
Date: 11/21/2011 10:27:00 PM
Version: Microsoft Solver Foundation 3.0.2.10889 Standard Edition
Model Name: DefaultModel
Capabilities Applied: MILP
Solve Time (ms): 367
Total Time (ms): 489
Solve Completion Status: Optimal
Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver
Algorithm: Primal
Arithmetic: Hybrid
Variables: 1 -> 1 + 2
Rows: 2 -> 2
Nonzeros: 2
Eliminated Slack Variables: 0
Pricing (exact): SteepestEdge
Pricing (double): SteepestEdge
Basis: Slack
Pivot Count: 1
Phase 1 Pivots: 0 + 0
Phase 2 Pivots: 1 + 0
Factorings: 4 + 1
Degenerate Pivots: 0 (0.00 %)
Branches: 0
===Solution Details===
Goals:
goal_8ef: -5

Decisions:
x: 5
===== Finished .\output.mps: 00:00:00.5501834 =====

This is incorrect. The reported value of x=5 indicates x is not read as a binary variable. If we solve the MPS file with CBC we see:

C:\Users\erwin\Documents>..\Downloads\cbc output.mps -solve -solution stdout
Welcome to the CBC MILP Solver
Version: 2.7.5
Build Date: Nov 10 2011
Revision Number: 1759

command line - ..\Downloads\cbc output.mps -solve -solution stdout (default strategy 1)
At line 1 NAME          MODEL
At line 2 ROWS
At line 5 COLUMNS
At line 9 RHS
At line 11 BOUNDS
At line 12 ENDATA
Problem MODEL has 1 rows, 1 columns and 1 elements
Coin0008I MODEL read with 0 errors
Continuous objective value is -1 - 0.00 seconds
Cgl0004I processed model has 0 rows, 0 columns (0 integer) and 0 elements
Cbc3007W No integer variables - nothing to do
Cuts at root node changed objective from -1 to -1.79769e+308
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                -1.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.01
Time (Wallclock seconds):       0.01

Optimal - objective value -1.00000000
      0 x                      1                     -1
Total time (CPU seconds):       0.02   (Wallclock seconds):       0.02


C:\Users\erwin\Documents>

The output is a little bit confusing, but indeed x assumes the value 1. This confirms x is binary.

Wednesday, November 16, 2011

Rick Rosenthal: Ten Keys to Success in Optimization Modeling

I recently talked to a an ex-student of Rick Rosenthal. The following presentation contains some concise descriptions of his ideas and beliefs on modeling:

http://faculty.nps.edu/rrosent/docs/rosenthalAtlanta.ppt

HPC applications in the Amazon cloud

From http://aws.amazon.com/hpc-applications/:

“For example, a 1064 instance (17024 cores) cluster of cc2.8xlarge instances was able to achieve 240.09 TeraFLOPS for the High Performance Linpack benchmark, placing the cluster at #42 in the November 2011 Top500 list.”

Monday, November 14, 2011

Sulum Optimization

Bo Jensen at http://www.sulumoptimization.com announced the availability of a new commercial LP solver. Some first impressions:
  • LP (+network) only for now, MIP will come later.
  • Aggressively priced compared to the big ones (Cplex, Gurobi). I can see this can be a very attractive offering in certain cases.
  • But it has a nasty license manager (somehow I always have troubles with these). The other commercial guys have similar drawbacks.
  • I think if you have a single license you can solve one LP at the time (a result of the previous point).
  • Low level API. In many cases, to be efficient you will need to use some more advanced modeling tools.
The product seems to be well-positioned between the Open Source offerings such as Lp-Solve, GLPK and CBC and the heavy guns (Cplex, Gurobi, Xpress).

Update: Unfortunately Sulum Optimization Tools are discontinued as per June 2015.

Wednesday, November 9, 2011

Automatic Reformulations

More and more we see that modeling systems apply automatic reformulations.

For instance I see that Cplex’s Concert accepts

model.add (IloMin (x, y) == 0)

for x≥0,y≥0. Essentially this is “x=0 or y=0”. This construct seems to get translated into

a+b≥1
a=1 ↔ x = 0
b=1 ↔ y = 0
x,y≥0, a,b∈{0,1}

Here the indicator constraints of Cplex are used, so no upper-bounds are needed. For other MIP solvers one would likely use something like:

x ≤ b * x.up
y ≤ (1-b) * y.up
x,y≥0, b∈{0,1} 

Similarly in the language CMPL we see that x*y is accepted and translated if x or y is a binary or integer variable (see http://www.coliop.org/download/cmpl/CMPL-1-5-2.pdf section 7.3).

Tuesday, November 8, 2011

Solver Options

In general I don’t like to use solver options to improve performance. I would hope that a solver would do a good job with default settings. Hopefully it will figure out from the model what settings it should use, an if not, will detect slow performance and does something about it. In addition I often feel that my own solver settings are not that stable. A next version of the solver may well show slower performance with my own settings, and a next version of the model may have similar issues. Also there is this statement I have heard someone saying: “each solver option is a situation where the developer did not know what to do”. Sometimes I notice users are very impressed by the many options a solver offers (may be also intimidated by the sometimes obscure but very technically advanced sounding descriptions). Here I almost argue the opposite. As a result, I often spent more time on model reformulations than on solver options.

But sometimes the differences are so dramatic, I have to break my own rules:

C:\projects\lsi\src\Development\TMS\Source\TestResults\erwin_ERWIN-THINK 2011-11-07 14_32_27\Out>type model.oml
Model[
Decisions[
Integers[0, 58],           This model is a little bit ugly as it was generated automatically by SaveModel.
Foreach[                   However it shows it is pretty small. 
{iter1, 59},
x[iter1]
]
],
Constraints[
prereq0 -> x[13] < x[0],
prereq1 -> x[20] < x[1],
prereq2 -> x[17] < x[2],
prereq3 -> x[7] < x[3],
prereq4 -> x[19] < x[4],
prereq5 -> x[26] < x[5],
prereq6 -> x[8] < x[6],
prereq7 -> x[21] < x[7],
prereq8 -> x[4] < x[8],
prereq9 -> x[12] < x[10],
prereq10 -> x[0] < x[11],
prereq11 -> x[18] < x[12],
prereq12 -> x[3] < x[13],
prereq13 -> x[9] < x[14],
prereq14 -> x[27] < x[15],
prereq15 -> x[5] < x[16],
prereq16 -> x[15] < x[17],
prereq17 -> x[6] < x[18],
prereq18 -> x[16] < x[19],
prereq19 -> x[22] < x[20],
prereq20 -> x[23] < x[21],
prereq21 -> x[14] < x[22],
prereq22 -> x[25] < x[23],
prereq23 -> x[10] < x[24],
prereq24 -> x[24] < x[25],
prereq25 -> x[2] < x[26],
prereq26 -> x[1] < x[27],
prereq27 -> x[29] < x[28],
prereq28 -> x[31] < x[29],
prereq29 -> x[32] < x[30],
prereq30 -> x[33] < x[31],
prereq31 -> x[28] < x[32],
prereq32 -> x[36] < x[34],
prereq33 -> x[34] < x[35],
prereq34 -> x[38] < x[36],
prereq35 -> x[35] < x[37],
prereq36 -> x[42] < x[39],
prereq37 -> x[39] < x[40],
prereq38 -> x[44] < x[40],
prereq39 -> x[45] < x[40],
prereq40 -> x[49] < x[40],
prereq41 -> x[53] < x[40],
prereq42 -> x[54] < x[40],
prereq43 -> x[56] < x[40],
prereq44 -> x[56] < x[41],
prereq45 -> x[56] < x[42],
prereq46 -> x[56] < x[43],
prereq47 -> x[50] < x[44],
prereq48 -> x[52] < x[45],
prereq49 -> x[57] < x[45],
prereq50 -> x[56] < x[46],
prereq51 -> x[56] < x[47],
prereq52 -> x[39] < x[48],
prereq53 -> x[44] < x[48],
prereq54 -> x[45] < x[48],
prereq55 -> x[49] < x[48],
prereq56 -> x[53] < x[48],
prereq57 -> x[54] < x[48],
prereq58 -> x[56] < x[48],
prereq59 -> x[43] < x[49],
prereq60 -> x[46] < x[49],
prereq61 -> x[56] < x[50],
prereq62 -> x[56] < x[52],
prereq63 -> x[41] < x[53],
prereq64 -> x[47] < x[54],
prereq65 -> x[40] < x[55],
prereq66 -> x[48] < x[55],
prereq67 -> x[51] < x[56],
prereq68 -> x[56] < x[57],
alldiff -> Unequal[Foreach[
{iter2, 59},
x[iter2]
]]
]
]

C:\projects\lsi\src\Development\TMS\Source\TestResults\erwin_ERWIN-THINK 2011-11-07 14_32_27\Out>"\Program Files (x86)\Microsoft Solver Foundation\3.0.2.10889\Bin\MSFCli.exe" +verbose 0 model.oml
===== Processing .\model.oml =====
Solution Quality: Feasible
===Solver Foundation Service Report===
Date: 11/8/2011 11:09:55 PM
Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition
Model Name: DefaultModel
Capabilities Applied: CP
Solve Time (ms): 184798    Timings with default settings
Total Time (ms): 185031
Solve Completion Status: Feasible
Solver Selected: Microsoft.SolverFoundation.Solvers.ConstraintSystem
===Solution Details===
Goals:
===== Finished .\model.oml: 00:03:05.0714386 =====

C:\projects\lsi\src\Development\TMS\Source\TestResults\erwin_ERWIN-THINK 2011-11-07 14_32_27\Out>"\Program Files (x86)\Microsoft Solver Foundation\3.0.2.10889\Bin\MSFCli.exe" +variable conflictdriven +verbose 0 model.oml
===== Processing .\model.oml =====
Solution Quality: Feasible
===Solver Foundation Service Report===
Date: 11/8/2011 11:06:38 PM
Version: Microsoft Solver Foundation 3.0.2.10889 Express Edition
Model Name: DefaultModel
Capabilities Applied: CP
Solve Time (ms): 203      Timings with option       
Total Time (ms): 433
Solve Completion Status: Feasible
Solver Selected: Microsoft.SolverFoundation.Solvers.ConstraintSystem
===Solution Details===
Goals:
===== Finished .\model.oml: 00:00:00.4739553 =====

Note: it is not surprising that Cplex added a tuning option to suggest some good settings. A related effort is: http://www.cs.ubc.ca/labs/beta/Projects/MIP-Config/.

Monday, November 7, 2011

Finding feasible schedules for a column generation algorithm

For a complex scheduling application, I need to generate a large number of feasible schedules for a class. Basically:

find x[1]…x[n] in {1..n}
under some precedence constraints x[i] < x[j]
all-different(x[1]…x[n])

MIP models are not very good for this (see http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/sorting-by-mip.html). But a constraint programming model should be very easy to formulate and may perform quite good.

With Microsoft Solver Foundation I had to use some nondefault settings (VariableSelection=ConfictDriven) to get good performance. Genererating multiple solutions is easily performed with Solution.GetNext(). I don’t think it is easy to generate a subset of solutions that has a certain spread. The only thing that comes to mind is doing many calls to Solution.GetNext() and just using each K-th solution. As I don’t know in advance how many solutions there are, I am thinking about increasing K as we go.

For some classes I have simply a very large number of possible schedules (or differently put: not enough precedence constraints to reduce this number). To find a reasonable subset we could augment the above system of equations with a random objective. Now we need to restate the objective each cycle, so we no longer can use Solution.GetNext().

From what I see most modeling systems have available constraint programming support (e.g. Ilog OPL, MS Solver Foundation) or have something announced (AMPL, AIMMS).

Update: link from comment below: www.nicta.com.au/pub?doc=4759.