Discrete Location Problems Benchmarks Library

Supply
Management Problem |

The Supply Management Problem with Lower-Bounded Demands (SMPLD) was initially formulated in (Chauhan

et al., 2004). In this problem a set of providers supply product of one type to a set of consumers, the quantity of product that can be delivered lies between the given minimum and maximum values, and the costs proposed by each provider are linear functions of the quantity being delivered if the shipment is opened. The SMPLD consists in ¯nding the quantity of product which will be supplied by each provider to each consumer minimizing the total cost The mathematical formulation of SMPLD is:

(1)

(2)

(3) (4) (5) Here

mis the number of suppliers;nis the number of consumers; variableszijindicate the presence of delivery from a providerito a consumerj, whilexijrepresent the shipment size.Ajis the minimal amount of product required for the consumerj;mijis the minimum quantity the provideriis prepared to deliver to the consumerj;Miis the maximum quantity the provideriis able to deliver in total. Parametersaij ; cij ;mij ;Mi;Ajare supposed to be nonnegative and integer, although the integrality is not essential in this paper.Many practical problems in logistics, scheduling and production planning can be modeled as SMPLD or contain it as an important special case { see e.g. (Sun

et al., 1998; Shenget al., 2006).In case all

mij= 0 and the overall supply is equal to the overall demand, i.e.this problem becomes the well-known Fixed Charge Transportation Problem (FCTP) - see e.g. (Barr

et al., 1981; Sunet al., 1998).The SMPLD is also closely related to the supply management problem (SMP) considered by Chauhan and Proth (2003) and Chauhan

et al.(2005a). The first difference between SMP and SMPLD is that instead of inequality (2), in the SMP holds an equalityThe second di®erence is that in the SMP the cost functions are more general, namely, non-decreasing and concave. Finding any feasible solution to the SMP is NP-hard even for

n= 1, yet there exists a pseudopolynomial-time exact algorithm for it (Chauhanet al., 2005a).The SMPLD is also NP-hard (it contains the minimum knapsack problem as a special case) and finding a feasible solution satisfying (2){(5) is NP-hard even in the case

n= 2. However, in casen= 1, this problem admits a fully polynomial time approximation scheme (FPTAS) and there is a fast greedy 2-approximation algorithm for it (Chauhanet al., 2004). An FPTAS forn= 1 and more general form of the cost functions is developed in (Chauhanet al., 2005b). At the same time, in the SMPLD, unlike SMP, consumption of goods is not given in advance, but only bounded from below, thus yielding larger linear relaxation polyhedron.

References1. Barr, R.S., R.S. Glover and D. Klingman (1981). A new optimization method for large scale fixed charge transportation problems.

Oper. Res.29(3), 448–463.2. Chauhan, S.S. and J.-M. Proth (2003). The concave cost supply problem.

Europ. Journ. of Oper. Res.148(2), 374–383.3. Chauhan, S.S., A.V. Eremeev, A.A. Kolokolov and V.V. Servakh (2005

a). Concave cost supply management problem for single manufacturing unit. In:Supply Chain Optimisation, Product/Process Design, Facility Location and Flow Control(A. Dolgui, J. Soldek and O. Zaikin, Eds.). Springer Verlag. pp. 167–174.4. Chauhan, S.S., A.V. Eremeev, A.A. Romanova and V.V. Servakh (2004). Approximation of linear cost supply management problem with lower-bounded demands. In:

Proc. of Discrete Optimization Methods in Production and Logistics (DOM`2004). pp. 16–21. Omsk.