GeCO

Generators for Combinatorial Optimization

This python package offers functionality to easily create instances for combinatorial optimization problems like knapsack or facility location. By making use of well known open source libraries such as NetworkX for graphs and PySCIPOpt for mathematical programming, the created instances can be used directly or saved to disk in a variety of different file formats. Releases of GeCO get pushed to PyPI, which makes it easy to install it into the python distribution of your choice via pip.

Short Example

Assume you want a knapsack instance like in this paper by Yang et al.

To generate an instance with 5 items and save it to disc you would simply run:

from geco import knapsack

knapsack_model = knapsack.yang.yang_instance(n=5, seed=1)
knapsack_model.writeProblem("yang_n5.mps")

Installation

The mixed integer programming part of the code heavily depends on the python interface of SCIP: PySCIPOpt. The easiest way to install it is using conda

conda install -c scipopt pyscipopt

If you prefer installing SCIP yourself or using an existing installation of SCIP on your system, you can follow this guide for installing pyscipopt.

Then, once you have pyscipopt installed, you are ready to install the geco package.

pip install geco

That's it, now you are ready to generate some instances!

Extended Example

Assume you want a knapsack instance like in the Yang et al. paper.

You start by looking through the knapsack package, then searching for a file with the name FIRSTAUTHOR.py. In this case we find a yang.py file in the mips/knapsack package.

To generate an instance with 5 items you would run

from geco import knapsack

knapsack_model = knapsack.yang.yang_instance(n=5, seed=1)

This, as all generators inside the mips subpackage, returns a PySCIPOpt model that makes use of the SCIP mixed integer programming solver, refer to their docs to learn how to set params, solve the instance and a lot more.

Randomization

As you might have noticed the generator function has a seed parameter, as a matter of fact this is common through out all generators that exhibit random behavior, it is used to preserve the random state, in order to get a random instance each time you can use seed=None.

Multiple instance generation

In case you want to generate more than one instance, we have created some helpful generator functions in the generator.py.

To generate n instances you can use the generate_n function, an example to generate 10 Yang knapsack instances would be

from geco.generator import generate_n
from geco.mips.knapsack import yang

for model in generate_n(lambda seed: yang.yang_instance(n=5, seed=seed), n=10):
    model.optimize()

There is also another function generate which is more flexible, assuming you don't know exactly how many instance you might require, it works the exact same way it just doesn't stop after n instances are generated.

MIPLIB

MIPLIB 2017 instances can be loaded into a PySCIPOpt model using the Loader class.

from geco.mips.loading.miplib import Loader

instance = Loader().load_instance('INSTANCE_NAME.mps.gz')

Implemented Generators

All the following instances are implemented following some of the generation techniques found in the literature, please refer to the modules corresponding to the generating function for a reference to where it was introduced.

MIPS

• Capacitated Facility Location
• Scheduling
• Knapsack
• Set Packing
• Set Cover
• Production Planning
• Maximum Independent Set
• Maximum Cut
• Packing
• Graph Coloring

Graphs

• Chimera (Selby)
• Pegasus

Contributing

If you want to add some new generator, fix a bug or enhance the repository in some way, please refer to our guide.