Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Primal Heuristics
verfasst von : Debora Mahlke
Erschienen in: A Scenario Tree-Based Decomposition for Solving Multistage Stochastic Programs
Verlag: Vieweg+Teubner
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
So far, we have mainly concentrated on improving the formulation of the problem yielding a better lower bound of the linear program relaxation. A further important aspect in a branch-and-cut algorithm is the generation of good feasible solutions early in the solution process with the aim of reducing the overall computational effort. Thus, in this chapter we focus on the development of a primal heuristic, aiming at the generation of solutions with a low objective function value in an adequate running time. ding the deterministic as well as the stochastic problem, a variety of primal approaches can be found in the literature, generally classified into construction and improvement heuristics. In order to obtain a good feasible start solution for the branch-and-cut algorithm, we follow the idea of
relax-and-fix
, which constructs a feasible solution from scratch. Thereon, we adapt this approach to our problems by developing problem specific approximation schemes, which are used additionally to the integrality relaxation.