November 2021

Symmetry-less 1D bin packing

16 November 2021 (2,326 words)

Symmetry-less 1D bin packing

Recently we were working on a small one-dimensional bin packing model. The situation was simple, and we expected the model to be easy to solve. But there was just one problem: we couldn't find an optimal solution, even after letting the solver run overnight for 12 hours.

Initially, we were using the CBC solver. Since that didn't work, we tried CPLEX via NEOS, but we encountered the same problem – CPLEX couldn't find an optimal solution either.

So, we searched the Operations Research literature for an alternative formulation. We discovered a recently published academic paper that has a new, innovative formulation for one-dimensional bin packing (and potentially other types of packing situations).

This article describes the new formulation and our experience applying it to our simple, yet difficult to solve, model.

CMPL 2.0 optimization tool

5 November 2021 (199 words)


There are many tools for building an optimization model, including:

  • Excel/OpenSolver, which provides a familiar, interactive, visual grid for modelling.
  • Python, plus the CVXPY or PuLP library, which provides a programmatic way to define a model.

Each tool has advantages and disadvantages, as we discussed in Optimization in Excel vs Python.

The tool CMPL (<Coliop|Coin> Mathematical Programming Language) occupies an intermediate position. That is, CMPL combines the advantages of working with the data and solution in Excel, while providing the power and flexibility of a programming language for defining the model.

According to the tool's website:

The CMPL syntax is similar in formulation to the original mathematical model but also includes syntactic elements from modern programming languages. CMPL is intended to combine the clarity of mathematical models with the flexibility of programming languages.

Steglich, M. (2021). "Optimisation Modelling with Excel and CMPL2"

CMPL has recently been updated to version 2.0, as described in the paper "Optimisation modelling with Excel and CMPL2". The paper provides a good overview of CMPL, including a couple of examples to help you get started*.

* Note that there's a bug in the paper's transhipment example. You'll need to add minCap[edges] to the definition in line 01 of Listing 7.

Results 1 - 2 of 2