Thursday, February 12, 2009

Easy MIP

In this post we showed a very difficult mip model with just 217 0-1 variables. Here is a very large MIP model that shows the opposite behavior. Although it has about 230k integer variables, Cplex devours it: 


---   122,284 rows  352,038 columns  667,797 non-zeroes
---   231,136 discrete-columns
 
        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
  
      0     0   588575.0000   606                 588575.0000    14792        
      0     0   588575.0000   689                   Cuts: 313    16547        
      0     0   588575.0000   736                ZeroHalf: 14    17624        
*     0+    0                       587775.0000   588575.0000    17624    0.14%
      0     2   588575.0000   349   587775.0000   588575.0000    17624    0.14%
Elapsed real time =  30.14 sec. (tree size =  0.00 MB, solutions = 1)
*    10+    1                       588575.0000   588575.0000    18686    0.00%

Total turnaround time (including GAMS): 46 seconds. A good illustration that size of the problem is not a good indicator for difficulty. (Don't know much about the model as it was sent to me in LP format. There may be many variables automatically integer-valued).
Posted by at
Labels:

2 comments:

  1. larrydagFebruary 13, 2009 at 2:26 PM

    Erwin,

    Great blog. I would like to link it on my blog if you will
    http://industrialengineertools.blogspot.com/

    If I could make a suggestion. It would help your indexing if you put a list of the tags for your posts. This will help to easily find pertinent posts. It should be a simple widget in blogger.

    ReplyDelete
  2. Erwin KalvelagenFebruary 13, 2009 at 5:00 PM

    That sounds like a good idea. I have not been very disciplined in adding labels to my posts, so I would need to recheck them. In the mean time the search box at the top should help you finding past postings.

    ReplyDelete

Subscribe to: Post Comments (Atom)