Metamorphic is a (largely experimental) tree-decomposition-based solver for integer linear programs (ILPs). Unlike many other ILP solvers, Metamorphic uses neither branch-and-bound nor any kind of relaxation. Instead, it uses a dynamic programming algorithm largely inspired by this paper. Note that Metamorphic isn't intended to be a general-purpose ILP solver and it can be expected to effectively solve only ILPs with small incidence treewidth.
Metamorphic solves ILPs:
- That have a low incidence treewidth.
- In which each variable has explicit, finite lower and upper bounds that fit in a sized 16-bit integer. Ideally, these bounds should be as close to each other as possible.
It does this in the following order:
- It reads an ILP instance from the given input file, builds an incidence graph for it. Supported input formats are LP and MPS.
- It computes a nice tree decomposition for the incidence graph.
- It solves the instance using dynamic programming over the computed nice tree decomposition.
- If the instance is solved to optimality/feasibility, then an optimal/feasible solution is saved as a Gurobi SOL file.
As of now, we don't ship any precompiled binaries, so you'll have to download the sources and compile them yourself...
The good news is that running cargo build --release is all you'll need to do.
If you're not familiar with Cargo, you can find out more here.
Once you have compiled Metamorphic (which may take some time), you have two options: you can either run it in command-line mode or in interactive mode.
Command-line mode is how most command-line programs are used: you call the program by typing its name and listing all its arguments one after another in a command line. For example:
metamorphic my_ilp_instance.mps tcauto logfile logmd
This means: solve the ILP instance from my_ilp_instance.mps using an automatically determined number of worker threads while saving logs in the Markdown format on a disk.
Call metamorphic --help for more detail.
To launch the interactive mode, call metamorphic without any additional arguments.
The demo of the interactive mode is shown in the animation above.
Metamorphic is now in pre-release. It works as intended and solves problems but breaking changes in its interface are possible in the coming future.

