Title: Fast Matroid Intersection and Applications

Authors:  Francisco Sena (INESC-ID and IST, ULisboa)

Abstract: Matroids are a very useful abstraction in mathematics and combinatorial optimization allowing to model many different problems, such as optimal spanning trees, optimal  arborescences, and optimal assignments. General-purpose algorithms can then be used to solve instances of many different problems. The issue with these general algorithms is that
their complexity is usually higher than that of problem specific algorithms. One of those general algorithms is the matroid intersection algorithm, which also plays an important role in other general matroid algorithms.
The aim of this work is to study a new implementation of the matroid intersection algorithm based on recent techniques proposed from a theoretical point of view. Those techniques might allow us to obtain a general intersection algorithm with a complexity closer to that of problem specific algorithms. Hence, exact and approximate algorithms will be implemented and evaluated for their practical applicability on different problems.

Title:  Finding Attractive Solutions for Curbside Waste Collection

Authors:  Maria Cândida Mourão (ISEG, CMAFcIO, ULisboa), João Janela (ISEG, REM/CEMAPRE, ULisboa), Leonor Santiago Pinto (ISEG, REM/CEMAPRE, ULisboa)

Abstract: This talk focuses on a curbside waste collection problem in Portuguese municipality that is modelled as an extended mixed capacitated arc routing problem, which is known to be NP–hard. The proposed methodology uses: i) a GIS (Geographic Information System), available at the municipality, for the input/output stages as well as to reduce problem dimensions; ii) one matheuristic that iteratively solves a new hybrid model; iii) a two-phase matheuristic, that can be classified as a cluster first/routing second method; and iv) a variant of the later that, after releasing some of the assignments made in the first phase, gives the model some freedom to pursue better feasible solutions. Both two-phase matheuristics aim to identify connected and compacted trips. The quality of the generated solutions is accessed through the total routing time, as well as with some attractiveness measures. These measures evaluate the adequacy of the solutions to the real case–study, a crucial aspect for trips that need to be accepted by practitioners. Computational results with 265–1223 nodes and 492–2254 links, point to the good performance of the proposed methodology.

Acknowledgment: This work was partially supported by the Projects CEMAPRE/REM - UIDB /05069/2020 and CMAFcIO - UIDB/04561/2020, financed by FCT/MCTES through national funds.

Title: 

Authors: Antonio Diglio (University of Naples Federico II, Naples, Italy), Juanjo Peiró (University of Valencia, Burjassot, Spain), Carmela Piccolo (University of Naples Federico II, Naples, Italy) and Francisco Saldanha-da-Gama (CMAFcIO, ULisboa)

Abstract: In this talk, a districting problem with stochastic demands is investigated. The goal is to divide a geographic area into p contiguous districts such that, with some given probability, the districts are balanced with respect to some given lower and upper thresholds. The problem is cast as a p-median problem with contiguity constraints that is further enhanced with chance-constrained balancing requirements. The total assignment cost of the territorial units to the representatives of the corresponding districts is used as a surrogate compactness measure to be optimized. A two-phase heuristic is developed to solve the problem. The latter embeds a simulation procedure for estimating the probability of a given solution to yield a balanced districting, which also provides information for guiding the changes to make in the solution. The results of a series of computational tests performed are discussed based upon a set of testbed instances randomly generated. Finally, the talk discusses the proposal of an approximate deterministic counterpart for the problem at hand and new solution algorithms devised exploiting the introduced mathematical formulation.

Title: Comparison of Formulations for the Inventory Routing Problem

Authors: Ivana Ljubić (ESSEC) and C. Archetti ESSEC)

Abstract: In this work we propose an analysis and comparison of the strength of the lower bound, measured as the value of the linear programming relaxation, of different formulations for the Inventory Routing Problem (IRP). In particular, we first focus on aggregated formulations, i.e., formulations where variables have no index associated with vehicles, and we analyse the link between compact formulations and their counterparts involving exponentially many constraints. We show that they are equivalent in terms of value of the linear relaxation. In addition, we study the link between aggregated and disaggregated formulations, i.e., formulations where variables have an index related to vehicles.
Also in this case, we show that aggregated and disaggregated formulations are equivalent in terms of the value of the corresponding linear relaxation. To the best of our knowledge, this analysis has never been done for the IRP, which instead is gaining a lot of popularity in the literature. Finally, we propose different exact solution approaches based on the aggregated formulations and we compare them with state-of-the-art exact methods for the IRP. Results show that the approaches based on aggregated formulations are competitive in terms of quality of both upper and lower bounds.

Title: Indicator-based branch and bound for multi-objective combinatorial optimization

Authors: Alexandre D. Jesus (CISUC, DEI, University of Coimbra), Luís Paquete (CISUC, DEI, University of Coimbra), Bilel Derbel (CNRS, Inria, University of Lille) and Arnaud Liefooghe (CNRS, Inria, University of Lille)

Abstract: We introduce an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next node to be processed is chosen with respect to the quality of its upper bound. This quality is given by a binary quality indicator, such as the binary hypervolume or the ????-indicator, with respect to the archive of solutions maintained by the branch and bound algorithm. Although the I-BB will eventually identify the efficient set, we are particularly interested in analyzing its anytime behavior as a heuristic. Our experimental results, conducted on the multi-objective knapsack problem with 2, 3, 5, and 7 objectives, indicate that the I-BB can often outperform the naive depth-first and breadth-first branch and bound search strategies, both in terms of runtime and anytime performance. The improvement is especially significant when the branching order for the decision variables is random, which suggests that the I-BB is particularly relevant when more favorable (problem-dependent) branching orders are not available. Based on these experimental results, we introduce an I-BB variant that changes search strategies during its execution to further improve the anytime performance of the approach.

Title: The Hamiltonian p-Median Problem: Polyhedral Results and Branch-and-Cut Algorithm

Authors: Michele Barbato (Dipartimento di Informatica “Giovanni degli Antoni” - Università degli Studi di Milano) and Luis Gouveia (CMAFcIO, ULisboa)

Abstract: The Hamiltonian p-median problem is to partition the n vertices of a graph G into p cycles of minimum total weight. We strengthen an MILP on edge variables withy two families of inequalities:
i) the quasi-Hamiltonian cycle inequalities which are associated to cycles not spanning all nodes.
ii) restricted cut constraints whose shores have specific cardinalities and are valid for the cases n=3p and n=3p+1

We give facet-defining conditions for subsets of the inequalities above. We develop a branch-and-cut algorithm also enhanced by cost-based inequalities. It compares well to existing algorithms for the HpMP and solves 3 benchmark instances previously unsolved and 16 new LaRGER instances with up to 400 vertices.