Modeling Fixed Charges and Setup Costs

Introduces the fixed-charge structure in integer programming: how to model a one-time setup cost that is incurred only when an activity is performed at a positive level. Students learn to link a continuous activity variable to a binary indicator using big-M constraints, formulate single- and multi-activity total cost objectives, and choose the tightest valid big-M.

Step 1 of 157%

Tutorial

The Fixed-Charge Structure

In many real-world problems, a cost is incurred only when an activity is actually performed. If we produce zero units, we pay nothing. If we produce any positive amount, we pay a one-time fixed cost (or setup cost) in addition to a per-unit variable cost.

For a single activity with level $x \ge 0$ , the fixed-charge cost function is

C(x) = \begin{cases} 0 & \text{if } x = 0, \\ f + c\,x & \text{if } x > 0, \end{cases}

where $f$ is the fixed cost and $c$ is the variable cost per unit. This function is discontinuous at $x=0$ , so a plain linear program cannot represent it.

We linearize the fixed charge by introducing a binary indicator $y \in \{0,1\}$ with the interpretation

y = \begin{cases} 1 & \text{if the activity is performed,} \\ 0 & \text{if not.} \end{cases}

The total cost is then written as the linear expression

C = f\,y + c\,x,

and we add the linking constraint

x \le M\,y,

where $M$ is a known upper bound on $x$ .

This linking constraint enforces the fixed-charge logic. If $y=0$ , then $x \le 0$ , so $x=0$ and no cost is paid. If $y=1$ , then $x \le M$ , allowing production up to capacity, and the fixed charge $f$ is automatically added to the objective.