mmrbipy: A solver for the min-max regret binary integer programming problem (MMR-BIP)

Installation

In a virtual environment with Python 3.6+, mmrbipy can be installed via

pip install mmrbipy

Using mmrbipy

With a compatible instance file, mmrbipy solves the MMR-BIP from a Python script:

from mmrbipy import Model

# Generate a model from instance file
mod = Model(problem='kp', filename='../instance/KP/1-70-01-45-20')

# Solve by iDS algorithm with best-scenario constraints
mod.solve(algorithm='ids-b', timelimit=100)

# Print results
print("objective value: {}".format(mod.objval))
print("time to best: {:.2f}".format(mod.ttb))

# Write the results to file
mod.write("result.txt")

Model

To solve the MMR-BIP, mmrbipy provides five types of instance format:

• min-max binary integer programming problem (bip)
• min-max regret knapsack problem (kp)
• min-max regret multidimensional knapsack problem (mkp)
• min-max regret set covering problem (scp)
• min-max regret generalized assignment problem (gap)

See instance page for the details of each type

Set problem type in constructor of Model class

# Generate a model from instance file
mod = Model(problem='kp', filename='../instance/KP/1-70-01-45-20')

Note: Benchmark instances for

• min-max regret knapsack problem
• min-max regret multidimensional knapsack problem
• min-max regret set covering problem
• min-max regret generalized assignment problem

are available in the instance directory on the project's homepage. For easy access to the example files, we recommend cloning the repository.

Algorithm

To solve the MMR-BIP, mmrbipy provides the following algorithms:

• fixed scenario algorithm (fix);
• Benders-like decomposition algorithm (bd);
• branch-and-cut algorithm with Benders cuts (bc);
• dual substitution algorithm (ds);
• iterated dual substitution algorithm with best-scenario constraints (ids-b);
• iterated dual substitution algorithm with Hamming-distance constraints (ids-h);
• branch-and-cut algorithm for dual substitution model with best-scenario constraints (bcds-b);
• branch-and-cut algorithm for dual substitution model with Hamming-distance constraints (bcds-h).

Set algorithm type in solve function

# Solve by iDS algorithm with best-scenario constraints
mod.solve(algorithm='ids-b', timelimit=100)

Note: The implement are based on gurobypy.

Additional information

For more information about the algorithms used in the solver, see Wu et al. (2022).