EURO Journal on Computational Optimization

In this paper, we consider the target visitation problem (TVP) which arises in the context of disaster treatment. Mathematically speaking, the problem is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance travelled, a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinatorial optimization problems: the traveling salesman and the linear ordering problem. In this paper, we point out some polyhedral properties, develop a branch-and-cut algorithm for solving the TVP to optimality and present some computational results.

For many practical applications it is important to determine not only a numerical approximation of one but a representation of the whole set of globally optimal solutions of a non-convex optimization problem. Then one element of this representation may be chosen based on additional information which cannot be formulated as a mathematical function or within a hierarchical problem formulation. We present such an application in the field of robotic design. This application problem can be modeled as a smooth box-constrained optimization problem. We extend the well-known $$\alpha \hbox {BB}$$ method such that it can be used to find an approximation of the set of globally optimal solutions with a predefined quality. We illustrate the properties and give a proof for the finiteness and correctness of our modified $$\alpha \hbox {BB}$$ method.

In this study, we propose exact solution methods for the split delivery vehicle routing problem (SDVRP). We first give a new vehicle-indexed flow formulation for the problem and then a relaxation obtained by aggregating the vehicle-indexed variables over all vehicles. This relaxation may have optimal solutions where several vehicles exchange loads at some customers. We cut off such solutions, in a nontraditional way, either by extending the formulation locally with vehicle-indexed variables or by node splitting. We compare these approaches using instances from the literature and new randomly generated instances. Additionally, we introduce two new extensions of the SDVRP by restricting the number of splits and by relaxing the depot return requirement and modify our algorithms to handle these extensions.

This paper investigates a portfolio optimization problem under uncertainty on the stock returns, where the manager seeks to achieve an appropriate trade-off between the expected portfolio return and the risk of loss. The uncertainty set consists of a finite set of scenarios occurring with equal probability. We introduce a new robustness criterion, called pw-robustness, which seeks to maximize the portfolio return in a proportion p of scenarios and guarantees a minimum return over all scenarios. We model this optimization problem as a mixed-integer programming problem. Through extensive numerical experiments, we identify the instances that can be solved to optimality in an acceptable time using off-the-shelf software. For the instances that cannot be solved to optimality within the time frame, we propose and test a heuristic that exhibits excellent practical performance in terms of computation time and solution quality for the problems we consider. This new criterion and our heuristic methods therefore exhibit great promise to tackle robustness problems when the uncertainty set consists of a large number of scenarios.

In this study, we investigate a hybrid Lagrangian relaxation ant colony optimisation for optimisation version of the car sequencing problem. Several cars are required to be scheduled on an assembly line and each car requires a number of options such as sunroof and/or air conditioning. These cars are required to be sequenced such that sub-sequences of specific sizes may only include a limited number of any option. While this is usually a hard constraint, in this study we treat it as a soft constraint and further require the utilisation of options be modulated across the sequence leading to the optimisation problem. We investigate various Lagrangian heuristics, ant colony optimisation (ACO) and hybrids of these methods. The results show that the Lagrangian-ACO hybrid is the best performing method for up to 300 cars.