Initializing help system before first use

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 DEMANDpt 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 SETUPCOSTt is associated with production in a period, and the total production capacity per period, CAPt, is limited. The unit production cost PRODCOSTpt per product and time period is also given. There is no inventory or stock-holding cost.

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

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

minimize
∑
t ∈ TIMES
(SETUPCOSTt ·
∑
p ∈ PRODUCTS
setuppt +
∑
p ∈ PRODUCTS
PRODCOSTpt · producept )
∀ p ∈ PRODUCTS, t ∈ TIMES:
t
∑
s = 1
produceps ≥
t
∑
s = 1
DEMANDps
∀ p ∈ PRODUCTS, t ∈ TIMES: producept ≤ DptT · setuppt
∀ t ∈ TIMES:
∑
p ∈ PRODUCTS
producept ≤ CAPt
∀ p ∈ PRODUCTS, t ∈ TIMES: setuppt ∈ {0,1}, producept ≥ 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 Dptl stands for the demand of product p in periods t to l. The production capacity per period t is limited. And finally, the setuppt variables are binaries.

Cutting plane algorithm

A well-known class of valid inequalities for ELS are the so-called (l,S)-inequalities [PW94]. If Dptl 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
producept +
l
∑
t = 1 | t ∉ S
Dptl · setuppt ≥ Dp1l

It says that actual production producept in the periods included in S plus the maximum potential production Dptl · setuppt 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:

  1. Solve the LP.
  2. Identify violated (l,S)-inequalities by testing violations of
    l
    ∑
    t = 1
    min(producept, Dptl · setuppt) ≥ Dp1l
  3. Add violated inequalities as cuts to the problem.
  4. 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).

Parent Topic Solving several model instances in parallel

© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.