Various (integer) linear modeling tricks

Note

This article was originally posted to the AIMMS Tech Blog.

Modeling problems with an (integer) linear program sometimes requires some experience to recognize certain structures in the problem description that can be formulated in a linear way.

On the website of the Naval Postgraduate School, you can find the document Formulating Integer Linear Programs: A Rogues’ Gallery that tries to demystify the art of formulating linear and integer linear programs. They do this by introducing formulettes, which consist of a verbal description and the constraints and variables that model this verbal description.

The first simple example of a formulette they provide is the following:

For each unit of \(X_1\) , there must be at least 5 units of \(X_2\)

which can be modeled with

\(5X_1 \le X_2\)

The document contains a lot more of such formulettes of varying complexity.

Furthermore, in our book Optimization Modeling you can also find various modeling tricks in the chapters Linear Programming Tricks and Integer Programming Tricks. The Optimization Modeling book can either be found online via the link above, or you can find it under the Help menu after you started AIMMS.

Last Updated: October, 2019