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