3 Presentations

• 
  02:00 PM - 02:30 PM

  Bi-Objective Variable Neighborhood Search for the p-Diversity-Proximity Problem

  • Behnaz Saboonchi, presenter, GERAD - HEC Montréal
  • Pierre Hansen, HEC Montréal
  • Sylvain Perron, GERAD, HEC Montréal

  Application of the dispersion models in order to address the cannibalization phenomenon within franchised chains is a recent approach. These models focus on the maximization of dispersion among the same-brand units without considering their proximity to the customer zones. In this work we have designed a bi-objective location model which is aimed at maximizing the minimum distance among the new located units while minimizing their gravity-based distance to the customer zones. This unique model captures simultaneously two of the most importance concerns within the franchise location domain, for the first time in the literature. We finally develop a heuristic solution procedure based on the Bi-objective Variable Neighborhood Search (BOVNS) framework in order to create high-quality solutions for both objectives in the Pareto front. Extensive computational experiments are also presented.

• 
  02:30 PM - 03:00 PM

  Routing and Wavelength Assignment Problem with Geodesics in Realistic Optical Transport Network Topologies

  • Martin Cousineau, presenter, McGill University
  • Sylvain Perron, GERAD, HEC Montréal
  • Gilles Caporossi, GERAD, HEC Montréal
  • Marcia Paiva, Federal University of Espirito Santo
  • Marcelo Segatto, Federal University of Espirito Santo

  This paper presents a decomposition approach for solving a variant of the Routing and Wavelength Assignment (RWA) problem, in which all connection requests are covered by geodesics, i.e., shortest paths with respect to a given cost function. In this paper we compute them with respect to the number of hops. Our decomposition approach is an extension of a recent method proposed in the literature, for the case of geodesics. We also improve this method by proposing new ways of selecting the set of promising paths in the paths selection phase. Our approach as well as an integer linear optimization formulation are tested on 29 realistic optical transport networks (OTN) ranging from 9 to 100 nodes. The results show that our approach can find the optimal number of wavelengths or an interval on this number in a short computing time. We also show that this interval can be used to accelerate the solution process of the integer linear formulation. Using these techniques, we were able to find and prove the optimal number of wavelengths for 28 of the 29 networks while providing a small interval on the optimal number of wavelengths for the remaining network. To the best of our knowledge, the RWA problem is solved with proof of optimality for the first time for such a number of realistic topologies. Furthermore, since the main assumptions made in this paper correspond to a worst-case scenario, our results can be used as an upper bound to other variants of the RWA problem.

• 
  03:00 PM - 03:30 PM

  The Maximum Ratio Clique Problem

  • Samyukta Sethuraman, presenter, Texas A&M University
  • Sergiy Butenko, Texas A&M University

  This paper introduces a fractional version of the classical maximum weight clique problem, the maximum ratio clique problem. Given a simple undirected graph G=(V,E) with the set V={1,..., n} of vertices, a clique is a subset of vertices inducing a complete subgraph. A maximal clique is a clique that is not a subset of a larger clique, and a maximum clique is a clique with the maximum possible number of vertices in the graph. Given a non-negative weight w_i associated with each vertex i in V, the maximum weight clique problem is to find a clique that maximizes the sum of its vertex weights. The case where w_i=1 for all i in V corresponds to the classical maximum clique problem, which has numerous applications in diverse areas
  From an applied perspective, cliques are typically used to model cohesive subgroups or clusters in a network representation of a certain complex system, where one wants to maximize the overall weight of a cluster. However, in some cases a fractional objective function provides a more appropriate description of the underlying goal. For example, in a variation of the market graph, where the vertices represent stocks and the edges correspond to pairs of stocks with negative correlations of price fluctuations, a maximal clique describes a diversified portfolio of stocks, referred to as a clique portfolio. It is assumed that the buying price and projected selling price of a fixed number of shares of stock is given. Then finding a clique portfolio with the maximum projected return requires maximizing the ratio of the total selling prices to the total cost prices of the clique vertices. Other examples of applications of the maximum ratio clique problem include social networks and construction of wind farms for utilizing renewable sources of energy.
  The problem is formally defined as: Given a simple undirected graph G=(V,E), where each vertex i in V, is assigned two non-negative weights, a_i and b_i, the maximum ratio clique problem (MRCP) is to find a maximal clique C in G that maximizes the ratio of the sum of a_j to the sum of b_j, where j refers to the index of a vertex in C.
  This work establishes the NP-completeness of the decision version of MRCP and provides an integer programming formulation with a fractional objective function. Three solution methods: linearization of formulation, binary search and Newton's method are proposed and compared using the results of numerical experiments on standard graph instances, as well as on real-life instances arising in finance and energy systems.
  Fractional objective functions have been studied for many classical problems in combinatorial optimization. Examples include the maximun ratio spanning tree problem and the fractional knapsack problem. However, to the authors' best knowledge, the maximum ratio clique problem has not been considered in literature. This work motivates and introduces this NP-complete problem, and provides methods for solving it to optimality.