Abstracts

• Nicolas Forget, Sune Lauth Gadegaard, Lars Relund Nielsen, Kathrin Klamroth, and Anthony Przybylski

• Computers & Operations Research, Volume 148, December 2022

• Abstract: The recent success of bi-objective Branch-and-Bound (B&B) algorithms heavily relies on the efficient computation of upper and lower bound sets. These bound sets are used as a supplement to the classical dominance test to improve the computational time by imposing inequalities derived from (partial) dominance in the objective space. This process is called objective branching since it is mostly applied when generating child nodes. In this paper, we extend the concept of objective branching to multi-objective integer optimization problems with three or more objective functions. Several difficulties arise in this case, as there is no longer a lexicographic order among non-dominated outcome vectors when there are three or more objectives. We discuss the general concept of objective branching in any number of dimensions and suggest a merging operation of local upper bounds to avoid the generation of redundant sub-problems. Finally, results from extensive experimental studies on several classes of multi-objective optimization problems is reported.

• Nicolas Forget, Sune Lauth Gadegaard, Lars Relund Nielsen

• European Journal of Operational Research, Volume 302, Issue 3, November 2022, Pages 909-924

• Abstract: In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. In the recent literature, competitive frameworks has been proposed for bi-objective 0–1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, however, the polyhedral structure of the linear relaxation becomes more complex, and consequently requires more computational effort to obtain. In this paper we overcome this obstacle by speeding up the computations. To do so, in each branching node we use information available from its father node to warm-start a Bensons-like algorithm. We show that the proposed algorithm significantly reduces the CPU time of the framework on several different problem classes with three, four and five objective functions. Moreover, we point out difficulties that arise when non-binary integer variables are introduced in the models, and test our algorithm on problem that contains non-binary integer variables too.

• Sune Lauth Gadegaard and Jens Lysgaard

• Discrete Applied Mathematics, Volume 296, June 2021, Pages 179-192

• Abstract: In this paper we propose a new polynomially sized formulation of the well known symmetric capacitated vehicle routing problem. Formulations of polynomial size have already been published in the academic literature for this problem, but they all possess the feature that they contain many equivalent solutions. As such, the optimal set of routes will be represented by several equivalent integer feasible solutions to the formulation, potentially leading to excessive computation times. The equivalence between solutions results from the possibility of reversing the order of visit on any route, starting and ending at the depot, without affecting feasibility or route length. In contrast, the formulation proposed in this paper eliminates the existence of equivalent integer solutions. In particular, instead of describing a route as a path starting and ending at the depot, we represent a route as two paths originating from the depot and ending at a so called peak customer on the route. Moreover, in our formulation there is only one possible peak customer for any such two paths, resulting in a unique representation of any route. Our formulation has shown very competitive computing times compared to a classical formulation of comparable size. Consequently, our formulation can be recommended in combination with the use of algebraic modeling languages for entering a formulation in its entirety into a mixed-integer linear programming solver.

• Sune Lauth Gadegaard, Lars Relunds Nielsen, and Matthias Ehrgott

• INFORMS Journal on Computing, Volume 31, Issue 4, June 2019, Pages 790-804

• Abstract: Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method that can generate all rational compromises between the objectives. This paper proposes two distinct bound set-based branch-and-cut algorithms for general bi-objective combinatorial optimization problems based on implicit and explicit lower-bound sets. The algorithm based on explicit lower-bound sets computes, for each branching node, a lower-bound set and compares it with an upper-bound set. The other fathoms branching nodes by generating a single point on the lower-bound set for each local nadir point. We outline several approaches for fathoming branching nodes, and we propose an updating scheme for the lower-bound sets that prevents us from solving the bi-objective linear programming relaxation of each branching node. To strengthen the lower-bound sets, we propose a bi-objective cutting-plane algorithm that adjusts the weights of the objective functions such that different parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy “Pareto branching.” We prove the effectiveness of the algorithms through extensive computational results.

• Sune Lauth Gadegaard, Andreas Klose, and Lars Relund Nielsen

• EURO Journal on Computational Optimization, Volume 6, Issue 1, March 2018, Pages 1-27

• Abstract: In this paper we propose a new polynomially sized formulation of the well known symmetric capacitated vehicle routing problem. Formulations of polynomial size have already been published in the academic literature for this problem, but they all possess the feature that they contain many equivalent solutions. As such, the optimal set of routes will be represented by several equivalent integer feasible solutions to the formulation, potentially leading to excessive computation times. The equivalence between solutions results from the possibility of reversing the order of visit on any route, starting and ending at the depot, without affecting feasibility or route length. In contrast, the formulation proposed in this paper eliminates the existence of equivalent integer solutions. In particular, instead of describing a route as a path starting and ending at the depot, we represent a route as two paths originating from the depot and ending at a so called peak customer on the route. Moreover, in our formulation there is only one possible peak customer for any such two paths, resulting in a unique representation of any route. Our formulation has shown very competitive computing times compared to a classical formulation of comparable size. Consequently, our formulation can be recommended in combination with the use of algebraic modeling languages for entering a formulation in its entirety into a mixed-integer linear programming solver.

• Sune Lauth Gadegaard, Andreas Klose, and Lars Relunds Nielsen

• Annals of Operations Research, Volume 267, Number 1, 2018, Pages 179-201

• Abstract: This paper considers a family of bi-objective discrete facility location problems with a cost objective and a bottleneck objective. A special case is, for instance, a bi-objective version of the (vertex) p-centdian problem. We show that bi-objective facility location problems of this type can be solved efficiently by means of an ε-constraint method that solves at most (𝑛−1)⋅𝑚 minisum problems, where n is the number of customer points and m the number of potential facility sites. Additionally, we compare the approach to a lexicographic ε-constrained method that only returns efficient solutions and to a two-phase method relying on the perpendicular search method. We report extensive computational results obtained from several classes of facility location problems. The proposed algorithm compares very favorably to both the lexicographic ε-constrained method and to the two phase method.

• S.L. Gadegaard

• Department of Economics and Business Economics, Aarhus University, June 2016

• Abstract: This PhD-dissertation proposes a number of solution procedures for discrete facility location problems. In the literature of operations research, location problems are mathematical models describing optimization problems where one or more facilities need to be placed in relation to a given set of customers or demand points. An example is the location of hospitals which needs to be performed in such a way as to take into account capacity limits and the sizes of nearby towns and cities.

The dissertation particularly focuses on the so-called single-source capacitated facility location problem (SSCFLP). The problem consists in opening a set of facilities and allocating the customers’ demands to these open facilities in such a way that the capacity of each facility is respected and such that each customer is serviced from exactly one open facility. An optimal solution to the SSCFLP is a solution in which the total cost of opening facilities and servicing customers is minimized. In this problem, it is assumed that all costs and the customers’ demand and the capacity of the facilities are fixed and known.

The dissertation proposes new solution procedures for both single objective as well as bi– objective versions of the SSCFLP. The dissertation considers exact methods that guarantee an optimal solution. When two objective functions are optimized simultaneously, an optimal solution consists of a set of solutions which maps into the entire set of non–dominated outcome vectors.

The first chapter of the dissertation provides a historic overview of location problems and a short survey of the literature on discrete multi–objective facility location.

The second chapter proposes an improved cut–and–solve based algorithm for the SSCFLP. The algorithm is effective and turns out to be up to 40 times faster compared to state-of-the-art algorithms from the literature.

The third chapter describes two algorithms that integrates the cut–and–solve framework with a semi-Lagrangean dual ascent algorithm in order to solve large instances of the SSCFLP. The first algorithm uses a variant of the cut–and–solve algorithm proposed in Chapter 2 to solve subproblems arising in the dual ascent algorithm whereas the second solves the sparse problems of the cut–and–solve algorithm using a semi–Lagrangean baseddual ascent algorithm.

In the last two chapters (Chapter 4 and Chapter 5) of the dissertation, bi-objective location problems are considered. In Chapter 4, a so-called bi-objective “cost-bottleneck” location problems is studied. The problem minimizes two objective functions simultaneously. The first minimizes the total cost while the second minimizes the maximal transportation time from a customer to a nearest open facility. An ε-constrained algorithm is proposed which preserves the structure of the underlying location problem. In the last chapter of the dissertation, Chapter 5, branch-and-cut algorithms for bi-objective optimization are developed. The proposed algorithms rely on explicitly and implicitly given lower bound sets and compute all rational compromises between the cost of opening facilities and the cost incurred by servicing the customers.

• S.L. Gadegaard

• www.optimization-online.org, April 2016

• Abstract: This paper describes how the cut-and-solve framework and semi-Lagrangean based dual ascent algorithms can be integrated in two natural ways in order to solve the single source capacitated facility location problem. The first uses the cut-and-solve framework both as a heuristic and as an exact solver for the semi-Lagrangean subproblems. The other uses a semi-Lagrangean based dual ascent algorithm to solve the sparse problems arising in the cut-and-solve algorithm. Furthermore, we developed a simple way to separate a special type of cutting planes from what we denote the effective capacity polytope with generalized upper bounds. From our computational study, we show that the semi-Lagrangean relaxation approach has its merits when the instances are tightly constrained with regards to the capacity of the system, but that it is very hard to compete with a standalone implementation of the cut-and-solve algorithm. We were, however, able to increase the size of the instances solvable by almost 25 percent compared to methodologies proposed in the literature.