|   | 
Details
   web
Records
Author Averbakh, I.; Pereira, J.
Title Lateness Minimization in Pairwise Connectivity Restoration Problems Type
Year 2018 Publication Informs Journal On Computing Abbreviated Journal INFORMS J. Comput.
Volume 30 Issue 3 Pages 522-538
Keywords combinatorial optimization; networks: scheduling; programming: branch and bound; network restoration; network construction; integrated network design and scheduling
Abstract A network is given whose edges need to be constructed (or restored after a disaster). The lengths of edges represent the required construction/restoration times given available resources, and one unit of length of the network can be constructed per unit of time. All points of the network are accessible for construction at any time. For each pair of vertices, a due date is given. It is required to find a construction schedule that minimizes the maximum lateness of all pairs of vertices, where the lateness of a pair is the difference between the time when the pair becomes connected by an already constructed path and the pair's due date. We introduce the problem and analyze its structural properties, present a mixed-integer linear programming formulation, develop a number of lower bounds that are integrated in a branch-and-bound algorithm, and discuss results of computational experiments both for instances based on randomly generated networks and for instances based on 2010 Chilean earthquake data.
Address [Averbakh, Igor] Univ Toronto Scarborough, Dept Management, Toronto, ON M1C 1A4, Canada, Email: averbakh@utsc.uturonto.ca;
Corporate Author Thesis
Publisher Informs Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1091-9856 ISBN Medium
Area Expedition Conference
Notes WOS:000449096000008 Approved
Call Number UAI @ eduardo.moreno @ Serial 924
Permanent link to this record
 

 
Author Lagos, F.; Pereira, J.
Title Multi-arme d bandit-base d hyper-heuristics for combinatorial optimization problems Type
Year 2023 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 312 Issue 1 Pages 70-91
Keywords Metaheuristics; Combinatorial optimization; Hyper-heuristics; Machine learning
Abstract There are significant research opportunities in the integration of Machine Learning (ML) methods and Combinatorial Optimization Problems (COPs). In this work, we focus on metaheuristics to solve COPs that have an important learning component. These algorithms must explore a solution space and learn from the information they obtain in order to find high-quality solutions. Among the metaheuristics, we study Hyper-Heuristics (HHs), algorithms that, given a number of low-level heuristics, iteratively select and apply heuristics to a solution. The HH we consider has a Markov model to produce sequences of low-level heuristics, which we combine with a Multi-Armed Bandit Problem (MAB)-based method to learn its parameters. This work proposes several improvements to the HH metaheuristic that yields a better learning for solving problem instances. Specifically, this is the first work in HHs to present Exponential Weights for Exploration and Exploitation (EXP3) as a learning method, an algorithm that is able to deal with adversarial settings. We also present a case study for the Vehicle Routing Problem with Time Windows (VRPTW), for which we include a list of low-level heuristics that have been proposed in the literature. We show that our algorithms can handle a large and diverse list of heuristics, illustrating that they can be easily configured to solve COPs of different nature. The computational results indicate that our algorithms are competitive methods for the VRPTW (2.16% gap on average with respect to the best known solutions), demonstrating the potential of these algorithms to solve COPs. Finally, we show how algorithms can even detect low-level heuristics that do not contribute to finding better solutions to the problem.& COPY
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:001060399900001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1877
Permanent link to this record
 

 
Author Ljubic, I.; Moreno, E.
Title Outer approximation and submodular cuts for maximum capture facility location problems with random utilities Type
Year 2018 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 266 Issue 1 Pages 46-56
Keywords Combinatorial optimization; Branch-and-cut; Maximum capture; Random utility model; Competitive facility location
Abstract We consider a family of competitive facility location problems in which a “newcomer” company enters the market and has to decide where to locate a set of new facilities so as to maximize its market share. The multinomial logit model is used to estimate the captured customer demand. We propose a first branch-and-cut approach for this family of difficult mixed-integer non-linear problems. Our approach combines two types of cutting planes that exploit particular properties of the objective function: the first one are the outer-approximation cuts and the second one are the submodular cuts. The approach is computationally evaluated on three datasets from the recent literature. The obtained results show that our new branch-and-cut drastically outperforms state-of-the-art exact approaches, both in terms of the computing times, and in terms of the number of instances solved to optimality. (C) 2017 Elsevier B.V. All rights reserved.
Address [Ljubic, Ivana] ESSEC Business Sch, 3 Av Bernard Hirsch,BP 50105, F-95021 Cergy Pontoise, France, Email: ivana.ljubic@essec.edu;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:000423646500005 Approved
Call Number UAI @ eduardo.moreno @ Serial 815
Permanent link to this record