The Express heuristic for probabilistically constrained integer problems

The Express heuristic for probabilistically constrained integer problems

0.00 Avg rating0 Votes
Article ID: iaor20132788
Volume: 19
Issue: 3
Start Page Number: 423
End Page Number: 441
Publication Date: Jun 2013
Journal: Journal of Heuristics
Authors: , ,
Keywords: programming: integer, heuristics
Abstract:

Integer problems under joint probabilistic constraints with random coefficients in both sides of the constraints are extremely hard from a computational standpoint since two different sources of complexity are merged. The first one is related to the challenging presence of probabilistic constraints which assure the satisfaction of the stochastic constraints with a given probability, whereas the second one is due to the integer nature of the decision variables. In this paper we present a tailored heuristic approach based on alternating phases of exploration and feasibility repairing which we call Express (Explore and Repair Stochastic Solution) heuristic. The exploration is carried out by the iterative solution of simplified reduced integer problems in which probabilistic constraints are discarded and deterministic additional constraints are adjoined. Feasibility is restored through a penalty approach. Computational results, collected on a probabilistically constrained version of the classical 0–1 multiknapsack problem, show that the proposed heuristic is able to determine good quality solutions in a limited amount of time.

Reviews

Required fields are marked *. Your email address will not be published.