Wicker Rod Problem

An Integer Programming Solver for The Wicker Rod Optimization Problem

To manufacture a wicker rattan box, $m_1$ pieces of length $l_1$, $m_2$ pieces of length $l_2$ and $m_3$ pieces of length $l_3$ are needed. For that, rods of length $l$ are provided. The goal of the producer is to find a batch size $b$ and the "recipe" that will allow the production of that batch while minimizing the absolute wicker waste.

Theoretical development

Can be found on theory.pdf. It's divided in the following sections:

1. Introduction: A basic, non technical introduction to the problem
2. Formalization and formulation: The necessary notions are formalized and the problem is formulated mathematically using this notions
3. Formulations as an IP problem: An Integer Programming equivalent version of the problem in section 2 is formulated.
4. Implementation details: Where some implementation caveats are explained

Implementation

The whole implementation can be found under solver.py. This solver is basically an adapter script on top of the python port for the IBM CPLEX solver for Integer Programming problems.

Instructions to run

Assuming that you have python3 and pip3 installed in your system, running the solver is pretty simple: Start by downloading the CPLEX port by executing on a terminal

pip3 install cplex

Then you can run the solver with the desired parameters

python3 solver.py l l1 l2 l3 m1 m2 m3 n_bound

where l is the rod length, l1 > l2 > l3 are the manufacturing lengths, m1, m2, m3 are the manufacturing multiplicities and the best solution found using a batch size of at most n_bound will be printed into STDOUT.

Running example

The following screenshot shows the output for the original problem's parameters, that motivated this development.