Portal de Periódicos da CAPES

Optimal Partition of an Interval — The Discrete Version

1993; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-46787-5_15

2196-9957

René Víctor Valqui Vidal,

Data Management and Algorithms

The optimal partition of an interval is a simple optimization problem which is formulated as follows: Given an interval, it is desired to partition it in N disjoint subintervals, so that a criterion function is maximized (or minimized). In this paper, we are dealing with the discrete version of this problem. This optimization problem has many applications as for instance in: inventory control, statistics, standardization, lot sizing, production planning, etc. In the past, this problem has been usually solved in a continuous version. The discrete version is a non-linear integer programming problem. We have implemented two general approaches to solve this problem: simulated annealing and dynamic programming. Extensive tests and numerical experiences will be reported. A well-known problem of optimal choice of sizes has been used as a case-study.