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

4 comments:

  1. Hi Erwin,

    I'm an Industrial Engineer student from Colombia and I'm trying to do a large scale scheduling for a study case.

    The situation as follows:

    There are 1454 jobs on 24 machines, so when I start to "solve" the MIP problem using Cplex, I always got the "out of memory" error.

    These are the parameters that I'm trying to use:

    $onecho > cplex.opt
    heurfreq -1
    mipinterval 1
    startalg 1
    subalg 1
    mipemphasis 4
    fraccuts -1
    solvelink 0
    names no
    threads 1
    memoryemphasis 1
    lpmethod 1
    decrease reinv
    nodefileind 3
    solvefinal 0
    nodesel 0
    varsel 3
    cuts -1
    barcrossalg -1
    workmem 1500
    $offecho
    jobshop.optfile=1;
    jobshop.dictfile=0;
    jobshop.holdfixed=1;

    Can you give me an advice?, am I doing something wrong?, Is feasible to have any solution?

    Thx a lot!

    ReplyDelete
  2. Answers: Yes, may be, don't know.

    Advice: ask someone to have a look at your model and the results. You can contact support@gams.com for that.

    ReplyDelete
  3. hi, im a post graduate student in MSC. i have a question. I have seen an example you made for TSP. I want to create a simple shortest path algorithm. Using Microsoft solver foundation i can see i can use LP to solve it. the only problem i have is that although i managed to make it work by adding edges and nodes with Ids (integers) i can seem to make it work with strings. i cant add string parameters and bid them with my arrays. I want this since i want to know to start and end node of each edge in order to form the constraints.
    I define 2 sets (edge and node, Domain.Any), parameters dist etc, it binds ok. But for the from and to parameters????

    Could you help me???? my mail is lefteris1029@hotmail.com

    ReplyDelete