Search

Binary Quadratic Program with Variable Partitioning Constraints The binary quadratic program with variable partitioning constraints is a very general class of optimization problems that is very difficult to solve because of the nonconvexity and integrality of the variables and is ubiquitous, among others, in network design, computer vision, and transportation and logistics. In their article, “A convex reformulation and an outer approximation for a large class of binary quadratic programs,” Rostami et al. show how to transform such a nonconvex challenging problem into a convex bilinear program with decomposable structure. The authors develop a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. The results of their computational experiments on different problems confirm the efficacy of the solution methods in solving large-scale problem instances.

In this paper, we consider a version of the capacitated vehicle routing problem (CVRP) where travel times are assumed to be uncertain and statistically correlated (CVRP-SCT). In particular, we suppose that travel times follow a multivariate probability distribution whose first and second moments are known. The main purpose of the CVRP-CST is to plan vehicle routes whose travel times are reliable, in the sense that observed travel times are not excessively dispersed with respect to their expected value. To this scope we adopt a mean-variance approach, where routes with high travel time variability are penalized. This leads to a parametric binary quadratic program for which we propose two alternative set partitioning reformulations and show how to exploit the structure of the correlation matrix when there is correlation only between adjacent links. For each model, we develop an exact branch-price-and-cut algorithm, where the quadratic component is dealt with either in the column generation master problem or in its subproblem. We tested our algorithms on a rich collection of instances derived from well-known data sets. Computational results show that our algorithms can efficiently solve problem instances with up to 75 customers. Furthermore, the obtained solutions significantly reduce the time variability when compared with standard CVRP solutions.

This paper considers the single allocation hub location problem under demand uncertainty where the allocation of the spokes to the hubs is optimized as second stage decision after the uncertainty in the demand is realized. We refer to this case as the variable allocation case, meaning that the allocation of the spokes to the hubs can be altered after the uncertainty is realized. This is in contrast to the fixed allocation case that is addressed in the literature, where the spokes are allocated to the chosen hubs before the uncertainty is realized. As shown in the paper, the fixed allocation case can be solved as a deterministic problem using the expected values of the random variables. However, the variable allocation model is a two-stage stochastic program that is challenging to solve. An alternative convex mixed-integer nonlinear formulation is presented for the variable allocation and a customized solution approach based on cutting planes is proposed to address the computational challenges. The proposed solution approach is implemented in a branch-and-cut framework where the cut-generating subproblems are solved combinatorially, i.e. without an optimization solver. Extensive computational results on the single allocation hub location problem and two of its variants, the capacitated case and the single allocation p-median problem are presented. The proposed cutting plane approach outperforms the direct solution of the problem using the state-of-the-art solver GUROBI as well the L-shaped decomposition, which is a common approach for addressing two-stage stochastic programs with recourse.

We study the single allocation hub location problem with heterogeneous economies of scale (SAHLP-h). The SAHLP-h is a generalization of the classical single allocation hub location problem (SAHLP), in which the hub-hub connection costs are piecewise linear functions of the amounts of flow. We model the problem as an integer nonlinear program, which we then reformulate as a mixed integer linear program (MILP) and as a mixed integer quadratically constrained program (MIQCP). We exploit the special structures of these models to develop Benders-type decomposition methods with integer subproblems. We use an integer L-shaped decomposition to solve the MILP formulation. For the MIQCP, we dualize a set of complicating constraints to generate a Lagrangian function, which offers us a subproblem decomposition and a tight lower bound. We develop linear dual functions to underestimate the integer subproblem, which helps us obtain optimality cuts with a convergence guarantee by solving a linear program. Moreover, we develop a specialized polynomial-time algorithm to generate enhanced cuts. To evaluate the efficiency of our models and solution approaches, we perform extensive computational experiments on both uncapacitated and capacitated SAHLP-h instances derived from the classical Australian Post data set. The results confirm the efficacy of our solution methods in solving large-scale instances.

The design of hub-and-spoke transport networks is a strategic planning problem, as the choice of hub locations has to remain unchanged for long time periods. However, strikes, disasters or traffic breakdown can lead to the unavailability of a hub for a short period of time. Therefore it is important to consider such events already in the planning phase, so that a proper reaction is possible; once a hub breaks down, an emergency plan has to be applied to handle the flows that were scheduled to be served by this hub. In this paper, we develop a two-stage formulation for the single allocation hub location problem which includes the reallocation of sources to a backup hub in case the hub breaks down. In contrast to related problem formulations from the literature, we keep the non-linear structure of the problem in our model. A branch-and-cut framework based on Benders decomposition is designed to solve large scale instances to proven optimality. Thanks to our decomposition strategy, we keep the structure of the resulting formulation similar to the classical single allocation hub location problem, which in turn allows to use classical linearization techniques from the literature. Our computational experiments show that this approach leads to a significant improvement in the performance when embedded into a standard mixed-integer programming solver. We report optimal solutions for instances much bigger than those solved so far in the literature.

In this paper we propose a new lower bounding procedure for the Quadratic Assignment Problem based on a generalization of the well-known Gilomore-Lawler procedure for a higher order reformulation. Computational results on some benchmark instances show the strength of the new approach compared with other lower bounds.

In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem (AQTSP). Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimal. We propose an extended Linear Programming formulation that has a variable for each cycle in the graph. Since the number of cycles is exponential in the graph size, we propose a column generation approach. Moreover, we apply a particular reformulation-linearization technique on a compact representation of the problem, and compute lower bounds based on Lagrangian relaxation. We compare our new bounds with those obtained by some linearization models proposed in the literature. Computational results on some set of benchmarks used in the literature show that our lower bounding procedures are very promising.

This paper proposes a new lower bounding procedure for the Uncapacitated Single Allocation p-Hub Median Problem based on Lagrangean relaxation. For solving the resulting Lagrangean subproblem, the given problem structure is exploited: it can be decomposed into smaller subproblems that can be solved efficiently by combinatorial algorithms. Our computational experiments for some benchmark instances demonstrate the strength of the new approach.

Hub location problems are strategic network planning problems. They formalise the challenge of mutually exchanging shipments between a large set of depots. The aim is to choose a set of hubs (out of a given set of possible hubs) and connect every depot to a hub so that the total transport costs for exchanging shipments between the depots are minimised. In classical hub location problems, the unit cost for transport between hubs is proportional to the distance between the hubs. Often these distances are Euclidean distances: Then it is possible to replace the quadratic cost term for hub-hub-transport in the objective function by a linear term and a set of linear inequalities. The resulting model can be solved by a row generation scheme. The strength of the method is shown by solving all AP instances to optimality.

International audience; We consider the problem of finding a shortest path in a directed graph with a quadratic objective func- tion (the QSPP). We show that the QSPP cannot be approximated unless P = NP . For the case of a convex objective function, an n -approximation algorithm is presented, where n is the number of nodes in the graph, and APX -hardness is shown. Furthermore, we prove that even if only adjacent arcs play a part in the quadratic objective function, the problem still cannot be approximated unless P = NP . In order to solve the problem we first propose a mixed integer programming formulation, and then devise an ef- ficient exact Branch-and-Bound algorithm for the general QSPP, where lower bounds are computed by considering a reformulation scheme that is solvable through a number of minimum cost flow problems. In our computational experiments we solve to optimality different classes of instances with up to 10 0 0 nodes.

The Minimum Spanning Tree Problem (MSTP) is one of the most known combinatorial optimization problems. It concerns the determination of a minimum edge-cost subgraph spanning all the vertices of a given connected graph. The Quadratic Minimum Spanning Tree Problem (QMSTP) is a variant of the MSTP whose cost considers also the interaction between every pair of edges of the tree. In this paper we review different strategies found in the literature to compute a lower bound for the QMSTP and develop new bounds based on a reformulation scheme and some new mixed 0-1 linear formulations that result from a reformulation-linearization technique (RLT). The new bounds take advantage of an efficient way to retrieve dual information from the MSTP reduced cost computation. We compare the new bounds with the other bounding procedures in terms of both overall strength and computational effort. Computational experiments indicate that the dual-ascent procedure applied to the new RLT formulation provides the best bounds at the price of increased computational effort, while the bound obtained using the reformulation scheme seems to reasonably tradeoff between the bound tightness and computational effort. HighlightsReview and analyzing different lower bounding strategies for the QMSTP.Using the meaning of reduced costs to develop new bounds.Developing two new bounds based on a reformulation scheme.Developing a new bound based on a second level of the RLT.Devising some efficient dual-ascent algorithms to solve the proposed models.

International audience; Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, but also by the combined presence of pairs of arcs in the solution. In this paper we model these situations as a Quadratic Shortest Path Problem, which calls for the minimization of a quadratic objective function subject to shortest-path constraints. We prove strong NP-hardness of the problem and analyze polynomially solvable special cases, obtained by restricting the distance of arc pairs in the graph that appear jointly in a quadratic monomial of the objective function. Based on this special case and problem structure, we devise fast lower bounding procedures for the general problem and show computationally that they clearly outperform other approaches proposed in the literature in terms of its strength.

The Reformulation Linearization Technique (RLT) applied to the Quadratic Assignment Problem yields mixed 0-1 programming problems whose linear relaxations provide a strong bound on the objective value. Nevertheless, in the high level RLT representations the computation requires much effort. In this paper we propose a new compact reformulation for each level of the RLT representation exploiting the structure of the problem. Computational results on some benchmark instances indicate the potential of the new RLT representations as the level of the RLT increases.

Recommender systems play an increasingly important role in online applications characterized by a very large amount of data and help users to find what they need or prefer. Various approaches for recommender systems have been developed that utilize either demographic, content, or historical information. Among these methods, item-based collaborative filtering is one of most widely used and successful neighborhood-based collaborative recommendation approaches that compute recommendation for users using the similarity between different items. However, despite their success, they suffer from the lack of available ratings which leads to poor recommendations. In this paper we apply a bi-criterion bath optimization approach on a graph representing the items and their similarity. This approach introduces additional similarity links by combining two or more existing links and improve the similarity matrix between items. The two criteria take into account on the one hand the distance between items on a the graph (min sum criterion), on the other hand the estimate of the information reliability (max min criterion). Experimental results on both explicit and implicit datasets shows that our approach is able to burst the accuracy of existing item-based algorithms and to outperform other algorithms.