Example problem: economic lot sizing

Economic lot sizing (ELS) considers production planning over a given planning horizon, in our example a range of time periods TIMES = 1,...,T. In every period t, there is a given demand DEMAND_pt for every product p (p ∈ PRODUCTS) that must be satisfied by the production in this period and by inventory carried over from previous periods.

A set-up cost SETUPCOST_t is associated with production in a period, and the total production capacity per period, CAP_t, is limited. The unit production cost PRODCOST_pt per product and time period is also given. There is no inventory or stock-holding cost.

We introduce the decision variables produce_pt for the amount of product p made in period t and the binary variables setup_pt indicating whether a setup takes place for product p in period t (setup_pt = 1) or not (setup_pt = 0).

We may then formulate the following mathematical model for this problem:

minimize

∑

_{t ∈ TIMES}

(SETUPCOST_t ·

∑

_{p ∈ PRODUCTS}

setup_pt +

∑

_{p ∈ PRODUCTS}

PRODCOST_pt · produce_pt )
∀ p ∈ PRODUCTS, t ∈ TIMES:

^t

∑

_{s = 1}

produce_ps ≥

^t

∑

_{s = 1}

DEMAND_ps
∀ p ∈ PRODUCTS, t ∈ TIMES: produce_pt ≤ D_ptT · setup_pt
∀ t ∈ TIMES:

∑

_{p ∈ PRODUCTS}

produce_pt ≤ CAP_t
∀ p ∈ PRODUCTS, t ∈ TIMES: setup_pt ∈ {0,1}, produce_pt ≥ 0

The objective function is to minimize the total cost. The constraints in the second line formulate the requirement that the production of p in periods 0 to t must satisfy the total demand for this product during this period of time. The next set of constraints establish the implication `if there is production during t then there is a setup in t' where D_ptl stands for the demand of product p in periods t to l. The production capacity per period t is limited. And finally, the setup_pt variables are binaries.

Cutting plane algorithm

A well-known class of valid inequalities for ELS are the so-called (l,S)-inequalities [PW94]. If D_ptl denotes the total demand of p in periods t to l, then for each period l and each subset of periods S of 1 to l, the (l,S)-inequality is

^l

∑

_{t = 1 | t ∈ S}

produce_pt +

^l

∑

_{t = 1 | t ∉ S}

D_ptl · setup_pt ≥ D_p1l

It says that actual production produce_pt in the periods included in S plus the maximum potential production D_ptl · setup_pt in the remaining periods (those not in S) must at least equal the total demand in periods 1 to l.

It is possible to develop the following cutting plane algorithm based on these (l,S)-inequalities:

Solve the LP.
Identify violated (l,S)-inequalities by testing violations of

^l

∑

_{t = 1}

min(produce_pt, D_ptl · setup_pt) ≥ D_p1l
Add violated inequalities as cuts to the problem.
Re-solve the LP problem.

There are numerous options for how to configure this algorithm. For instance:

Generation of cuts only in the root node or also during the search (Cut-and-Branch versus Branch-and-Cut).
Number of cut generation passes at a node (e.g. one pass or looping around steps 2.-4. until no more cuts are generated).
Search tree depth for cut generation (up to a given depth or at all nodes).
Exclusive use of (l,S)-cuts or combination with others (e.g. default cuts generated by the solver).

The implementation of the (l,S)-cut generation algorithm shown below may be configured to generate cuts at the top node only (TOPONLY = true) and to generate one or several rounds of cuts (SEVERALROUNDS = true).

Contents

Index

Glossary

Search Results

Example problem: economic lot sizing

Cutting plane algorithm