The maximum balanced subgraph of a signed graph: Applications and solution approaches

The Maximum Balanced Subgraph Problem (MBSP) is the problem of finding a subgraph of a signed graph that is balanced and maximizes the cardinality of its vertex set. This paper is the first one to discuss applications of the MBSP arising in three different research areas: the detection of embedded structures, portfolio analysis in risk management and community structure. The efficient solution of the MBSP is also in the focus of this paper. We discuss pre-processing routines and heuristic solution approaches to the problem. a GRASP metaheuristic is developed and improved versions of a greedy heuristic are discussed. Extensive computational experiments are carried out on a set of instances from the applications previously mentioned as well as on a set of random instances.     

General decay of solutions of a wave equation with memory term and acoustic boundary condition

In this paper, the global solvability to the mixed problem involving the wave equation with memory term and acoustic boundary conditions for non‐locally reacting boundary is considered. Moreover, the general decay of the energy functionality is established by the techniques of Messaoudi. Copyright © 2016 John Wiley & Sons, Ltd.     

A study on exponential-size neighborhoods for the bin packing problem with conflicts

We propose an iterated local search based on several classes of local and large neighborhoods for the bin packing problem with conflicts. This problem, which combines the characteristics of both bin packing and vertex coloring, arises in various application contexts such as logistics and transportation, timetabling, and resource allocation for cloud computing. We introduce \({\mathcal O}(1)\) evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighborhoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of good quality on the classical benchmark instances and scales very well with an increase of problem size. Extensive computational experiments are conducted to measure the respective contribution of each proposed neighborhood. In particular, the 0-cost moves and the large neighborhood based on set covering contribute very significantly to the search. Several research perspectives are open in relation to possible hybridizations with other state-of-the-art mathematical programming heuristics for this problem.     

An exact and heuristic approach for the <Emphasis Type="Italic">d</Emphasis>-minimum branch vertices problem

Given a connected graph \(G=(V,E)\), the d-Minimum Branch Vertices (d-MBV) problem consists in finding a spanning tree of G with the minimum number of vertices with degree strictly greater than d. We developed a Miller–Tucker–Zemlin based formulation with valid inequalities for this problem. The results obtained for different values of d show the effectiveness of the proposed method, which has solved several instances faster than previous methods. Also, an heuristic is proposed for this problem, that was tested on several instances of the Minimum Branch Vertices problem, which is the d-MBV problem, when \(d = 2\).     

Assuring the reliability of mass spectrometry for the routine determination of traces of doping in horse-urine

Summary This paper describes an analytical method using a nuclear-related technique for the detection of forbidden doping substances in the urine of race horses. The proposed method, adapted from the Méthode Alcaline Sur C-18 developed by the French Laboratoire de Contr?le Antidopage, is based on gas chromatography separation followed by mass spectrometry (GC-MS). The method was validated for caffeine, identified as the most frequent doping substance in the Brazilian horseracing activity. This validation is also a major requirement to achieve ISO/IEC 17025 laboratory accreditation. The validation has led to several metrological challenges because the decisions are largely based on qualitative results (“false-positive” and/or “false-negative”) and the degree of accuracy, as well as the traceability had to be determined in the absence of certified matrix reference materials.     

Alternative targets for data envelopment analysis through multi-objective linear programming: Rio de Janeiro Odontological Public Health System Case Study

In the last 10 years much has been written about the drawbacks of radial projection. During this time, many authors proposed methods to explore, interactively or not, the efficient frontier via non-radial projections. This paper compares three families of data envelopment analysis (DEA) models: the traditional radial, the preference structure and the multi-objective models. We use the efficiency analysis of Rio de Janeiro Odontological Public Health System as a background for comparing the three methods through a real case with one integer and one exogenous variable. The objectives of the study case are (i) to compare the applicability of the three approaches for efficiency analysis with exogenous and integer variables, (ii) to present the main advantages and drawbacks for each approach, (iii) to prove the impossibility to project in some regions and its implications, (iv) to present the approximate CPU time for the models, when this time is not negligible. We find that the multi-objective approach, although mathematically equivalent to its preference structure peer, allows projections that are not present in the latter. Furthermore, we find that, for our case study, the traditional radial projection model provides useless targets, as expected. Furthermore, for some parts of the frontier, none of the models provide suitable targets. Other interesting result is that the CPU-time for the multi-objective formulation, although its endogenous high complexity, is acceptable for DEA applications, due to its compact nature.     

Integer programming formulations and efficient local search for relaxed correlation clustering

Relaxed correlation clustering (RCC) is a vertex partitioning problem that aims at minimizing the so-called relaxed imbalance in signed graphs. RCC is considered to be an NP-hard unsupervised learning problem with applications in biology, economy, image recognition and social network analysis. In order to solve it, we propose two linear integer programming formulations and a local search-based metaheuristic. The latter relies on auxiliary data structures to efficiently perform move evaluations during the search process. Extensive computational experiments on existing and newly proposed benchmark instances demonstrate the superior performance of the proposed approaches when compared to those available in the literature. While the exact approaches obtained optimal solutions for open problems, the proposed heuristic algorithm was capable of finding high quality solutions within a reasonable CPU time. In addition, we also report improving results for the symmetrical version of the problem. Moreover, we show the benefits of implementing the efficient move evaluation procedure that enables the proposed metaheuristic to be scalable, even for large-size instances.