Given a simple undirected graph G, the Multiobjective Subgraph (MOS) problem aims to find a subgraph in G that maximizes the number of edges while minimizing the number of vertices. Addressing the MOS problem allows to solve the related Multiobjective Quasi-clique problem, which seeks a quasi-clique with maximum density and number of vertices and has many real-life applications. These problems have only been addressed using exact methods, which can be computationally intensive due to their NP-hard nature. In this paper, we introduce a heuristic method for solving the MOS problem. We show that a subset of optimal MOS subgraphs exhibits a nestedness property, meaning they satisfy an inclusion-wise relation. We explore this property to develop a path-relinking-based heuristic, where subgraphs from this subset serve as starting and ending points of a path to find new high-quality subgraphs. Additionally, we derive an upper bound on the number of edges for MOS subgraphs, which is used to evaluate the quality of the subgraphs generated by our heuristic. Experimental results on synthetic and real-life sparse graphs indicate that our heuristic produces high-quality subgraphs, with an average error of 2.3 edges compared to the exact method, while spending only 6.2% of its runtime.

Abstract We propose a multi-swarm approach to approximate the Pareto front of general multi-objective optimization problems that is based on the consensus-based optimization method (CBO). The algorithm is motivated step by step beginning with a simple extension of CBO based on fixed scalarization weights. To overcome the issue of choosing the weights we propose an adaptive weight strategy in the second modeling step. The modeling process is concluded with the incorporation of a penalty strategy that avoids clusters along the Pareto front and a diffusion term that prevents collapsing swarms. Altogether the proposed K-swarm CBO algorithm is tailored for a diverse approximation of the Pareto front and, simultaneously, the efficient set of general non-convex multi-objective problems. The feasibility of the approach is justified by analytic results, including convergence proofs, and a performance comparison to the well-known non-dominated sorting genetic algorithms NSGA2 and NSGA3 as well as the recently proposed one-swarm approach for multi-objective problems involving consensus-based optimization.

In many ridepooling applications transportation requests arrive throughout the day and have to be answered and integrated into the existing (and operated) vehicle routing. To solve this dynamic dial-a-ride problem we present a rolling-horizon algorithm that dynamically updates the current solution by solving an MILP formulation. The MILP model is based on an event-based graph with nodes representing pick-up and drop-off events associated with feasible user allocations in the vehicles. The proposed solution approach is validated on a set of real-word instances with more than 500 requests. In 99.5% of all iterations the rolling-horizon algorithm returned optimal insertion positions w.r.t. the current schedule in a time-limit of 30 seconds. On average, incoming requests are answered within 2.8 seconds.

Abstract A major difficulty in optimization with nonconvex constraints is to find feasible solutions. As simple examples show, the $$\alpha $$ α BB-algorithm for single-objective optimization may fail to compute feasible solutions even though this algorithm is a popular method in global optimization. In this work, we introduce a filtering approach motivated by a multiobjective reformulation of the constrained optimization problem. Moreover, the multiobjective reformulation enables to identify the trade-off between constraint satisfaction and objective value which is also reflected in the quality guarantee. Numerical tests validate that we indeed can find feasible and often optimal solutions where the classical single-objective $$\alpha $$ α BB method fails, i.e., it terminates without ever finding a feasible solution.

A problem of image registration is considered in the context of optimal mass transportation. The properties and limitations of an optimal image transportation are analyzed. A modified formulation of this approach is proposed in order to overcome the morphing effect. Finally, a fast and simple scale-space approach for the new formulation is introduced, and numerical examples are presented.