ZIB

1

Unknown

Two-row and two-column mixed-integer presolve using hashing-based pairing methods (2020)

Gemander, Patrick ; Chen, Wei-Kun ; Weninger, Dieter ; [et al.]

add to mindlist on the mindlist

Publication Date: 2023-11-03

Description: In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolve techniques successfully is their speed. Hence, most methods inspect constraints or variables individually in order to guarantee linear complexity. In this paper, we present new hashing-based pairing mechanisms that help to overcome known performance limitations of more powerful presolve techniques that consider pairs of rows or columns. Additionally, we develop an enhancement to one of these presolve techniques by exploiting the presence of set-packing structures on binary variables in order to strengthen the resulting reductions without increasing runtime. We analyze the impact of these methods on the MIPLIB 2017 benchmark set based on an implementation in the MIP solver SCIP.

Language: English

Type: article , doc-type:article

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

Overview

2

Unknown

Enabling research through the SCIP optimization suite 8.0 (2023)

Bestuzheva, Ksenia ; Besançon, Mathieu ; Chen, Wei-Kun ; [et al.]

add to mindlist on the mindlist

Details

Publication Date: 2024-09-19

Description: The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP.

Language: English

Type: article , doc-type:article

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

Overview

3

Unknown

The SCIP Optimization Suite 7.0 (2020)

Gamrath, Gerald ; Anderson, Daniel ; Bestuzheva, Ksenia ; [et al.]

add to mindlist on the mindlist

Details

Publication Date: 2024-09-19

Description: The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming frame- work SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies mixed-integer linear op- timization problems and can be used stand-alone or integrated into SCIP via a presolver plugin. SCIP 7.0 provides additional support for decomposition algorithms. Besides im- provements in the Benders’ decomposition solver of SCIP, user-defined decomposition structures can be read, which are used by the automated Benders’ decomposition solver and two primal heuristics. Additionally, SCIP 7.0 comes with a tree size estimation that is used to predict the completion of the overall solving process and potentially trigger restarts. Moreover, substantial performance improvements of the MIP core were achieved by new developments in presolving, primal heuristics, branching rules, conflict analysis, and symmetry handling. Last, not least, the report presents updates to other components and extensions of the SCIP Optimization Suite, in particular, the LP solver SoPlex and the mixed-integer semidefinite programming solver SCIP-SDP.

Language: English

Type: reportzib , doc-type:preprint

Format: application/pdf

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

PDF

Overview

4

Unknown

The SCIP Optimization Suite 8.0 (2021)

Bestuzheva, Ksenia ; Besançon, Mathieu ; Chen, Wei-Kun ; [et al.]

add to mindlist on the mindlist

Details

Publication Date: 2024-09-19

Description: The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type for cut selection, and a complete rework of the way nonlinear constraints are handled. Additionally, SCIP 8.0 now supports interfaces for Julia as well as Matlab. Further, UG now includes a unified framework to parallelize all solvers, a utility to analyze computational experiments has been added to GCG, dual solutions can be postsolved by PaPILO, new heuristics and presolving methods were added to SCIP-SDP, and additional problem classes and major performance improvements are available in SCIP-Jack.

Language: English

Type: reportzib , doc-type:preprint

Format: application/pdf

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

PDF

Overview