Browsing by Author "Rossi R."

Now showing 1 - 11 of 11

Citation - Scopus: 3
Computing Replenishment Cycle Policy Parameters for a Perishable Item*
(Vilnius Gediminas Technical University, 2010) Rossi R.; Tarim S.A.; Hnich B.; Prestwich S.D.
In many industrial environments there is a significant class of problems for which the perishable nature of the inventory cannot be ignored in developing replenishment order plans. Food is the most salient example of a perishable inventory item. In this work, we consider the periodic-review, single-location, single-product production/inventory control problem under non-stationary stochastic demand and service level constraints. The product we consider can be held in stock for a limited amount of time after which it expires and it must be disposed of at a cost. In addition to wastage costs, our cost structure comprises fixed and unit variable ordering costs, and inventory holding costs. We propose an easy-to-implement replenishment cycle inventory control policy that yields at most 2N control parameters, where N is the number of periods in our planning horizon. We also show, on a simple numerical example, the improvement brought by this policy over two other simpler inventory control rules of common use. © Izmir University of Economics, Turkey, 2010.
Citation - WoS: 8
Citation - Scopus: 10
Cost-Based Domain Filtering for Stochastic Constraint Programming
(2008) Rossi R.; Tarim S.A.; Hnich B.; Prestwich S.
Cost-based filtering is a novel approach that combines techniques from Operations Research and Constraint Programming to filter from decision variable domains values that do not lead to better solutions [7]. Stochastic Constraint Programming is a framework for modeling combinatorial optimization problems that involve uncertainty [9]. In this work, we show how to perform cost-based filtering for certain classes of stochastic constraint programs. Our approach is based on a set of known inequalities borrowed from Stochastic Programming - a branch of OR concerned with modeling and solving problems involving uncertainty. We discuss bound generation and cost-based domain filtering procedures for a well-known problem in the Stochastic Programming literature, the static stochastic knapsack problem. We also apply our technique to a stochastic sequencing problem. Our results clearly show the value of the proposed approach over a pure scenario-based Stochastic Constraint Programming formulation both in terms of explored nodes and run times. © 2008 Springer-Verlag Berlin Heidelberg.
Citation - WoS: 2
Citation - Scopus: 4
Cost-Based Filtering for Stochastic Inventory Control
(Springer Verlag, 2007) Tarim S.A.; Hnich B.; Rossi R.; Prestwich S.
An interesting class of production/inventory control problems considers a single product and a single stocking location, given a stochastic demand with a known non-stationary probability distribution. Under a widely-used control policy for this type of inventory system, the objective is to find the optimal number of replenishments, their timings and their respective order-up-to-levels that meet customer demands to a required service level. We extend a known CP approach for this problem using a cost-based filtering method. Our algorithm can solve to optimality instances of realistic size much more efficiently than previous approaches, often with no search effort at all. © Springer-Verlag Berlin Heidelberg 2007.
Citation - WoS: 3
Citation - Scopus: 5
A Cultural Algorithm for Pomdps From Stochastic Inventory Control
(Springer Verlag, 2008) Prestwich S.D.; Tarim S.A.; Rossi R.; Hnich B.
Reinforcement Learning algorithms such as SARSA with an eligibility trace, and Evolutionary Computation methods such as genetic algorithms, are competing approaches to solving Partially Observable Markov Decision Processes (POMDPs) which occur in many fields of Artificial Intelligence. A powerful form of evolutionary algorithm that has not previously been applied to POMDPs is the cultural algorithm, in which evolving agents share knowledge in a belief space that is used to guide their evolution. We describe a cultural algorithm for POMDPs that hybridises SARSA with a noisy genetic algorithm, and inherits the latter's convergence properties. Its belief space is a common set of state-action values that are updated during genetic exploration, and conversely used to modify chromosomes. We use it to solve problems from stochastic inventory control by finding memoryless policies for nondeterministic POMDPs. Neither SARSA nor the genetic algorithm dominates the other on these problems, but the cultural algorithm outperforms the genetic algorithm, and on highly non-Markovian instances also outperforms SARSA. © 2008 Springer Berlin Heidelberg.
Citation - Scopus: 12
Evolving Parameterised Policies for Stochastic Constraint Programming
(2009) Prestwich S.; Tarim S.A.; Rossi R.; Hnich B.
Stochastic Constraint Programming is an extension of Constraint Programming for modelling and solving combinatorial problems involving uncertainty. A solution to such a problem is a policy tree that specifies decision variable assignments in each scenario. Several solution methods have been proposed but none seems practical for large multi-stage problems. We propose an incomplete approach: specifying a policy tree indirectly by a parameterised function, whose parameter values are found by evolutionary search. On some problems this method is orders of magnitude faster than a state-of-the-art scenario-based approach, and it also provides a very compact representation of policy trees. © 2009 Springer Berlin Heidelberg.
Citation - Scopus: 5
Finding (?, ?)-Solutions Via Sampled Scsps
(2011) Rossi R.; Hnich B.; Tarim S.A.; Prestwich S.
We discuss a novel approach for dealing with single-stage stochastic constraint satisfaction problems (SCSPs) that include random variables over a continuous or large discrete support. Our approach is based on two novel tools: sampled SCSPs and (?, ?)-solutions. Instead of explicitly enumerating a very large or infinite set of future scenarios, we employ statistical estimation to determine if a given assignment is consistent for a SCSP. As in statistical estimation, the quality of our estimate is determined via confidence interval analysis. In contrast to existing approaches based on sampling, we provide likelihood guarantees for the quality of the solutions found. Our approach can be used in concert with existing strategies for solving SCSPs.
Citation - Scopus: 2
Neuroevolutionary Inventory Control in Multi-Echelon Systems
(2009) Prestwich S.D.; Tarim S.A.; Rossi R.; Hnich B.
Stochastic inventory control in multi-echelon systems poses hard problems in optimisation under uncertainty. Stochastic programming can solve small instances optimally, and approximately solve large instances via scenario reduction techniques, but it cannot handle arbitrary nonlinear constraints or other non-standard features. Simulation optimisation is an alternative approach that has recently been applied to such problems, using policies that require only a few decision variables to be determined. However, to find optimal or near-optimal solutions we must consider exponentially large scenario trees with a corresponding number of decision variables. We propose a neuroevolutionary approach: using an artificial neural network to approximate the scenario tree, and training the network by a simulation-based evolutionary algorithm. We show experimentally that this method can quickly find good plans. © 2009 Springer-Verlag Berlin Heidelberg.
Citation - WoS: 11
Citation - Scopus: 9
Replenishment Planning for Stochastic Inventory Systems With Shortage Cost
(Springer Verlag, 2007) Rossi R.; Armagan Tarim S.; Hnich B.; Prestwich S.
One of the most important policies adopted in inventory control is the (R,S) policy (also known as the "replenishment cycle" policy). Under the non-stationary demand assumption the (R,S) policy takes the form (R n,Sn) where Rn denotes the length of the n th replenishment cycle, and Sn the corresponding order-up-to-level. Such a policy provides an effective means of damping planning instability and coping with demand uncertainty. In this paper we develop a CP approach able to compute optimal (Rn,Sn) policy parameters under stochastic demand, ordering, holding and shortage costs. The convexity of the cost-function is exploited during the search to compute bounds. We use the optimal solutions to analyze the quality of the solutions provided by an approximate MIP approach that exploits a piecewise linear approximation for the cost function. © Springer-Verlag Berlin Heidelberg 2007.
Citation - WoS: 8
Citation - Scopus: 11
A Steady-State Genetic Algorithm With Resampling for Noisy Inventory Control
(2008) Prestwich S.; Tarim S.A.; Rossi R.; Hnich B.
Noisy fitness functions occur in many practical applications of evolutionary computation. A standard technique for solving these problems is fitness resampling but this may be inefficient or need a large population, and combined with elitism it may overvalue chromosomes or reduce genetic diversity. We describe a simple new resampling technique called Greedy Average Sampling for steady-state genetic algorithms such as GENITOR. It requires an extra runtime parameter to be tuned, but does not need a large population or assumptions on noise distributions. In experiments on a well-known Inventory Control problem it performed a large number of samples on the best chromosomes yet only a small number on average, and was more effective than four other tested techniques. © 2008 Springer-Verlag Berlin Heidelberg.
Citation - WoS: 3
Citation - Scopus: 5
Stochastic Constraint Programming by Neuroevolution With Filtering
(2010) Prestwich S.D.; Tarim S.A.; Rossi R.; Hnich B.
Stochastic Constraint Programming is an extension of Constraint Programming for modelling and solving combinatorial problems involving uncertainty. A solution to such a problem is a policy tree that specifies decision variable assignments in each scenario. Several complete solution methods have been proposed, but the authors recently showed that an incomplete approach based on neuroevolution is more scalable. In this paper we hybridise neuroevolution with constraint filtering on hard constraints, and show both theoretically and empirically that the hybrid can learn more complex policies more quickly. © 2010 Springer-Verlag.
Citation - WoS: 7
Citation - Scopus: 9
Synthesizing Filtering Algorithms for Global Chance-Constraints
(2009) Hnich B.; Rossi R.; Tarim S.A.; Prestwich S.
Stochastic Constraint Satisfaction Problems (SCSPs) are a powerful modeling framework for problems under uncertainty. To solve them is a P-Space task. The only solution approach to date compiles down SCSPs into classical CSPs. This allows the reuse of classical constraint solvers to solve SCSPs, but at the cost of increased space requirements and weak constraint propagation. This paper tries to overcome some of these drawbacks by automatically synthesizing filtering algorithms for global chance-constraints. These filtering algorithms are parameterized by propagators for the deterministic version of the chance-constraints. This approach allows the reuse of existing propagators in current constraint solvers and it enhances constraint propagation. Experiments show the benefits of this novel approach. © 2009 Springer Berlin Heidelberg.