Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • 2015-2019  (6)
  • 2019  (3)
  • 2016  (3)
Datenquelle
Erscheinungszeitraum
  • 2015-2019  (6)
Jahr
Sprache
  • 1
    facet.materialart.
    Unbekannt
    Structure-driven fix-and-propagate heuristics for mixed integer programming (2019)
    Details
    Publikationsdatum: 2022-03-14
    Beschreibung: Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60 % of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.
    Sprache: Englisch
    Materialart: article , doc-type:article
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 2
    facet.materialart.
    Unbekannt
    Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming (2016)
    Details
    Publikationsdatum: 2020-08-05
    Beschreibung: SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 3
    facet.materialart.
    Unbekannt
    Exploiting Dual Degeneracy in Branching (2019)
    Details
    Publikationsdatum: 2022-03-14
    Beschreibung: Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 4
    facet.materialart.
    Unbekannt
    Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming (2019)
    Details
    Publikationsdatum: 2020-11-23
    Beschreibung: The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.
    Sprache: Englisch
    Materialart: article , doc-type:article
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 5
    facet.materialart.
    Unbekannt
    SCIP-Jack – A solver for STP and variants with parallelization extensions (2016)
    Details
    Publikationsdatum: 2023-02-06
    Beschreibung: The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 6
    facet.materialart.
    Unbekannt
    The SCIP Optimization Suite 3.2 (2016)
    Details
    Publikationsdatum: 2024-01-12
    Beschreibung: The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...