Skip to Content

Using integer programming in R to optimize cargo loads

David Smith's picture

Linear Programming is a mathematical technique used to find the values of some variables (within the bounds of some defined constraints) to find the maximum value of a quantity. For example, consider this problem from the FishyOperations blog

A trading company is looking for a way to maximize profit per transportation of their goods. The company has a train available with 3 wagons. When stocking the wagons they can choose between 4 types of cargo, each with its own specifications. How much of each cargo type should be loaded on which wagon in order to maximize profit?

The quantity we want to optimize here is profit. The variables to consider are the cargo items selected to fill the wagons, each of which has its own volume and profit per tonne (and quantities aren't unlimited, either). The constraints are the weight and space capacities of the three wagons.

In actual fact, this is a mixed-integer linear programming problem: the cargo comes only in one-tonne lots, and can't be divided into fractional parts. Integer programming problems are notoriously difficult to solve, but the R package lpSolveAPI makes it easy with an R language interface to lp_solve, a powerful (and free!) mixed-integer program solver. (You can find a good overview to the lpSolveAPI package in this vignette.) Simply by defining the constraints in an R language script (for example, that the total cargo weight in wagon 1 can't exceed 5000 tonnes), the solve function finds the optimal solution to the model (expressed graphically below):

The maximum profit of $107,500 comes from shipping 5 tonnes of Cargo 2 and Cargo 3 in wagon 1, 8 tonnes of Cargo 4 in wagon 2, and 12 tonnes of Cargo 4 in wagon 3 (and not shipping any of Cargo 1 at all).

For more details of how the lpSolveAPI package can be used to solve mixed-integer linear programming problems (including the R script implementing this example), see the full blog post linked below.

Fishy Operations: Linear programming in R: an lpSolveAPI example (via Vadim Y. Bichutskiy)