Coins Tutorial: The Optimization Model

In order to formulate this as an optimization problem, we'll need to do three things.

• First, we'll need to define the decision variables. The goal of the optimization is to choose values for these variables.
• Second, we'll define a linear objective function. This is the function we'd like to minimize (or maximize).
• Third, we'll define the linear constraints.

The Gurobi Optimizer will consider all assignments of values to decision variables that satisfy the specified linear constraints, and return one that optimizes the stated objective function.

The variables in this problem are quite straightforward. The solver will need to decide how many of each coin to produce. It is convenient to give the decision variables meaningful names. In this case, we'll call the variables Pennies, Nickels, Dimes, Quarters, and Dollars. We'll also introduce variables that capture the quantities of the various minerals actually used by the solution. We'll call them Cu, Ni, Zi, and Mn.

Recall that the objective of our optimization problem is to maximize the total dollar value of the coins produced. Each penny produced is worth 0.01 dollars, each nickel is worth 0.05 dollars, etc. This gives the following linear objective:

  maximize: 0.01 Pennies + 0.05 Nickels + 0.1 Dimes + 0.25 Quarters + 1 Dollars

The constraints of this model come from the fact that producing a coin consumes certain quantities of the available minerals, and the supplies of those minerals are limited. We'll capture these relationships in two parts. First, we'll create an equation for each mineral that captures the amount of that mineral that is consumed. For copper, that equation would be:

  Cu = 0.06 Pennies + 3.8 Nickels + 2.1 Dimes + 5.2 Quarters + 7.2 Dollars

The coefficients for this equation come from the earlier coin specification table: one penny uses 0.06g of copper, one nickel uses 3.8g, etc.

The model must also capture the available quantities of each mineral. If we have 1000 grams of copper available, then the constraint would be:

  Cu <= 1000

For our example, we'll assume we have 1000 grams of copper and 50 grams of the other minerals.

There is actually one other set of constraints that must be captured in order for our model to accurately reflect the physical realities of our problem. While a dime is worth 10 cents, half of a dime isn't worth 5 cents. The variables that capture the number of each coin produced must take integer values.

Previous: Coins Tutorial: Problem Statement

Next: Coins Tutorial: The Model File

Further information

• How do I use the Gurobi Command Line Interface (gurobi_cl)?