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 N  obj E  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.

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.

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.

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

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.

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

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

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.