1,720,987 research outputs found
Branching on multi-aggregated variables
Full text linkAbstract. In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single vari-ables. This natural idea results in a hybrid between variable- and con-straint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Generic Branch-Cut-and-Price
No full textIn this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Improving strong branching by domain propagation
No full textOne of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way.
This paper extends previous work by the author published in the proceedings of the CPAIOR 2013
Improving strong branching by propagation
No full textStrong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers.
It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small.
In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching.
Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time
Verbesserte Vorhersagen und Strukturausnutzung im Branch-and-Bound-Verfahren
Full text linkMixed-integer linear programming (MIP) is an extremely successful tool to solve real-world optimization problems to optimality. The core algorithm used by state-of-the-art MIP solvers is the branch-and-bound method. It consists of two primary operations: branching splits a problem into smaller subproblems, and bounding uses upper and lower bounds to eliminate subproblems that can be proven not to contain improved solutions. In this thesis, we present methods that improve the branch-and-bound algorithm in both regards.
Most branching rules base their decisions on the predicted effect of the split of the subproblems. Since a good prediction can substantially reduce the number of subproblems that need to be processed, the first methods we discuss are focusing on the prediction quality. In order to perform a thorough computational analysis of the newly presented branching rules, we introduce the fair node number, a new measure for the quality of branching decisions. We present strong branching with domain propagation, which improves the dual bound predictions of strong branching by taking implications of the branching decision into account. Additionally, we propose different variants of lookahead branching, which not only consider the effects of the split on the created subproblems, but also regard how those subproblems can be split further.
Besides prediction quality, we focus on ways to improve the branch-and-bound method by exploiting structures in MIP instances. We present improvements of common MIP branching rules that exploit dual degeneracy, i.e., the presence of multiple LP optima, to improve prediction quality and reduce branching effort. We introduce cloud diameter branching, a branching rule based solely on degeneracy information, and degeneracy-aware hybrid branching, a rule that adjusts the importance of different measures based on the current degeneracy. Our novel branching on multi-aggregated variables rule splits the problem by branching on a general disjunction corresponding to multi-aggregation structures. To improve the bounding step, we present three structure-driven fix-and-propagate heuristics, which exploit structures present in many MIP instances to predict the impact of variable fixings and construct feasible solutions before the branch-and-bound process starts.
Implementations of the methods presented in this thesis are available in source code in the MIP solver SCIP 7.0. We present the results of extensive computational experiments that we conducted to demonstrate their effectiveness.Gemischt-ganzzahlige lineare Programmierung (MIP) ist ein erfolgreiches Mittel, um praktische Optimierungsprobleme zu lösen. Moderne MIP-Löser basieren auf dem Branch-and-Bound-Verfahren. Hierbei unterteilt der Branching-Schritt das Problem in Teilprobleme, während der Bounding-Schritt obere und untere Schranken an das Optimum nutzt, um Teilprobleme zu eliminieren, welche bewiesenermaßen keine verbessernde Lösung enthalten. Diese Arbeit behandelt Methoden, die diese beiden Hauptschritte des Branch-and-Bound-Verfahrens verbessern.
Die meisten Branching-Regeln treffen ihre Entscheidung basierend auf Vorhersagen, wie verschiedene Entscheidungen die Teilprobleme beeinflussen. Wir untersuchen Möglichkeiten, diese Vorhersagen zu verbessern, um bessere Branching-Entscheidungen zu treffen und somit die Anzahl der bearbeiteten Teilprobleme zu reduzieren. Hierfür definieren wir ein neues Maß, die faire Knotenzahl, welches wir nutzen, um die Qualität der getroffenen Entscheidungen mit Hilfe von Vergleichsrechnungen zu bewerten. Als Methoden präsentieren wir Strong Branching mit Domain Propagation und verschiedene Varianten des Lookahead Branching. Ersteres verbessert die Vorhersagen durch Anwendung von Reduktionen, welche aus der Branching-Entscheidung folgen, Letzteres betrachtet nicht nur den Effekt auf die erzeugten Teilprobleme, sondern auch mögliche nachgelagerte Teilungsoptionen.
Ein weiterer Fokus dieser Arbeit liegt auf dem Ausnutzen von Strukturen in MIP-Instanzen zur Verbesserung des Branch-and-Bound-Verfahrens. Wir untersuchen das Vorkommen alternativer Relaxierungsoptima, genannt duale Degeneriertheit, in praktischen Problemen und nutzen Degeneriertheit, um Vorhersagen zu verbessern und den Aufwand zu verringern. Wir präsentieren Cloud Diameter Branching, welches vollständig auf Degeneriertheitsinformationen basiert, während Degeneracy-aware Hybrid Branching diese Informationen nutzt, um die Gewichtung verschiedener Bewertungsfunktionen anzupassen. Außerdem stellen wir Branching auf multiaggregierten Variablen vor, welches aus Multiaggregationsstrukturen abgeleitete allgemeine Disjunktionen nutzt, um das Problem zu zerlegen. Die Anwendung des Bounding-Schritts schon zu Beginn des Lösungsprozesses ermöglichen die drei präsentierten strukturbasierten Startheuristiken, die häufig auftretende Strukturen nutzen, um Variablenfixierungen zu bestimmen und Lösungen zu konstruieren.
Implementierungen der präsentierten Methoden sind im Quelltext in Version 7.0 des MIP-Lösers SCIP verfügbar. Ihre Effektivität wird durch umfangreiche Rechenexperimente demonstriert.BMBF, 05M14ZAM, Forschungscampus MODAL - Mathematical Optimization and Data Analysis Laboratorie
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
