Introduction

In the realm of mathematical optimization, the choice of solver and parameter configuration can significantly impact the efficiency and quality of solutions. To gain insights into these aspects, we turn to MIPLIB, a renowned benchmark library for integer programming. In this blog post, we’ll explore the integration of Gurobi, a powerful optimization solver, with MIPLIB instances. By experimenting with different parameter sets, we aim to uncover valuable information about optimization performance.

Setting the Stage

Before delving into MIPLIB instances, let’s set up our environment. We start by installing the Gurobi Python package and importing the necessary libraries.

!pip install gurobipy &>/dev/null

import gurobipy as gp
from gurobipy import GRB
import time
import os
import urllib.request
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

MIPLIB Instances

Our benchmark instances are sourced from MIPLIB, providing a diverse set of optimization problems. We load the benchmark and collection files, preparing the instances for experimentation.

%%writefile benchmark.csv
gen-ip002
neos5
markshare2
pk1
mas74
mas76
assign1-5-8
neos859080
enlight_hard
glass-sc
mad
neos-3754480-nidda
graphdraw-domain
mik-250-20-75-4
neos-3046615-murg
glass4
timtab1
supportcase26
ran14x18-disj-8
fhnw-binpack4-4
neos-2657525-crna
neos17

%%writefile collection.csv
ej
stein9inf
stein15inf
flugpl
flugplinf
gen-ip016
gen-ip036
gen-ip054
enlight4
markshare_4_0
gen-ip021
gen-ip002
markshare_5_0
stein45inf
g503inf
gr4x6
markshare1
neos5
pk1
b-ball
p2m2p1m1p0n100
neos-1425699
enlight8
noswot
misc05inf
mas74
mas76
assign1-5-8
neos859080
enlight9
graphdraw-gemcutter
neos-5192052-neckar
gt2

with open("benchmark.csv", "r") as f:
  files = f.readlines()
benchmarkfiles = [entry.strip() for entry in files]

with open("collection.csv", "r") as f:
  files = f.readlines()
collectionfiles = [entry.strip() for entry in files]

Example MPS (Mathematical Programming System) Format

MPS format is a plain-text format designed to encode linear and mixed-integer programming problems. It stands as a bridge between model formulation and optimization solvers, providing a clear and concise representation of mathematical optimization problems. The format has been widely adopted due to its simplicity, making it easy for both humans and machines to read and interpret.

instance = benchmarkfiles[0]
url = 'https://miplib.zib.de/WebData/instances/' + instance +'.mps.gz'
urllib.request.urlretrieve(url,'gt2.mps.gz')
!gzip -d gt2.mps.gz
!cat gt2.mps

Building Optimization Models from MIPLIB Instances

instances = collectionfiles[0:10]

models=[]
for instance in instances:

  url = "https://miplib.zib.de/WebData/instances/" + instance + ".mps.gz"
  filename = instance +".mps.gz"
  urllib.request.urlretrieve(url, filename)
  model = gp.read(filename)
  model.setAttr("ModelName", instance)
  if model.IsMIP:
      models.append(model)

Experimenting with Parameters

Now, the heart of our exploration lies in experimenting with different Gurobi parameters. We focus on MIPSepCuts, CoverCuts, RelaxLiftCuts, and ZeroHalfCuts. By iterating through predefined parameter sets, we’ll observe their impact on optimization performance.

param_sets= [(x, y, z, w) for x in [-1, 0, 1] for y in [-1, 0, 1] for z in [-1, 0, 1] for w in [-1, 0, 1]]
params = ['MIPSepCuts','CoverCuts','RelaxLiftCuts','ZeroHalfCuts']

Running Experiments

We conduct experiments for each model and parameter set, capturing essential information such as solution time and status.

DD=[]
for model in models:
  print(model.ModelName)
  for paramset in param_sets:
    model.Params.OutputFlag = 0
    model.Params.TimeLimit = .05  #Max Time
    model.setParam(params[0],paramset[0])
    model.setParam(params[1],paramset[1])
    model.setParam(params[2],paramset[2])
    model.setParam(params[3],paramset[3])
    start_time = time.time()
    model.optimize()
    end_time = time.time()
    solution_time = end_time - start_time
   
    DD.append((model.ModelName, params[0],paramset[0], params[1],paramset[1], params[2],paramset[2], params[3],paramset[3],solution_time, model.Status == gp.GRB.OPTIMAL))

Visualization

To draw meaningful insights, we visualize the solution time across different parameter sets for each model using a heatmap.

df = pd.DataFrame(DD,columns=['Name'],)
df

df['Status'] = df[10].apply(lambda x: 'Optimal' if x else 'Infeasible')
df['ParamSet'] = '(' + df[2].astype(str) + ', ' + df[4].astype(str) + ', ' + df[6].astype(str) + ', ' + df[8].astype(str) + ')'
df['Time'] = df[9]
df['ModelName']=df[0]
df = df.sort_values(by=['Time'])
df.reset_index(drop=True, inplace=True)
df_plot = df.pivot_table(values='Time', index='ModelName', columns='ParamSet')
fig, ax = plt.subplots(figsize=(10, 6))
sns.heatmap(df_plot, annot=False, fmt=".2f", cmap='viridis')
plt.title('Solution Time by Parameter Set')
plt.xlabel('Parameter Set')
plt.ylabel('Model Name')
plt.show()

import plotly.express as px

fig = px.scatter(df, x="ModelName", y="Time", color="ParamSet", hover_data=['Status'])
fig.show()

Conclusion

By integrating Gurobi with MIPLIB instances, our experiments shed light on the impact of different parameter configurations. This analysis guides the selection of optimal parameters for specific problem types.