|   | 
Details
   web
Records
Author Ritt, M.; Pereira, J.
Title Heuristic and exact algorithms for minimum-weight non-spanning arborescences Type Journal Article
Year 2020 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 287 Issue 1 Pages 61-75
Keywords Minimum-weight non-spanning arborescence; Heuristic; Iterated Local Search; Branch-and-cut
Abstract We address the problem of finding an arborescence of minimum total edge weight rooted at a given vertex in a directed, edge-weighted graph. If the arborescence must span all vertices the problem is solvable in polynomial time, but the non-spanning version is NP-hard. We propose reduction rules which determine vertices that are required or can be excluded from optimal solutions, a modification of Edmonds algorithm to construct arborescences that span a given set of selected vertices, and embed this procedure into an iterated local search for good vertex selections. Moreover, we propose a cutset-based integer linear programming formulation, provide different linear relaxations to reduce the number of variables in the model and solve the reduced model using a branch-and-cut approach. We give extensive computational results showing that both the heuristic and the exact methods are effective and obtain better solutions on instances from the literature than existing approaches, often in much less time. (C) 2020 Elsevier B.V. All rights reserved.
Address [Ritt, Marcus] Univ Fed Rio Grande do Sul, Inst Informat, Av Bento Goncalves 9500, Porto Alegre, RS, Brazil, Email: marcus.ritt@inf.ufrgs.br;
Corporate Author Thesis
Publisher Elsevier 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:000541072800005 Approved no
Call Number UAI @ eduardo.moreno @ Serial 1187
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 Journal Article
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 no
Call Number UAI @ eduardo.moreno @ Serial 815
Permanent link to this record
 

 
Author Pereira, J.; Vasquez, O.C.
Title The single machine weighted mean squared deviation problem Type Journal Article
Year 2017 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 261 Issue 2 Pages 515-529
Keywords Scheduling; Single machine; JIT; Branch-and-cut; Dominance properties
Abstract This paper studies a single machine problem related to the just-In-Time (JIT) production objective in which the goal is to minimize the sum of weighted mean squared deviation of the completion times with respect to a common due date. In order to solve the problem, several structural and dominance properties of the optimal solution are investigated. These properties are then integrated within a branch and-cut approach to solve a time-indexed formulation of the problem. The results of a computational experiment with the proposed algorithm show that the method is able to optimally solve instances with up to 300 jobs within reduced running times, improving other integer programming approaches. (C) 2017 Elsevier B.V. All rights reserved.
Address [Pereira, Jordi] Univ Adolfo Ibanez, Dept Engn & Sci, Av Padre Hurtado 750,Off C216, Vina Del Mar, Chile, Email: jorge.pereira@uai.cl;
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:000401206300009 Approved no
Call Number UAI @ eduardo.moreno @ Serial 730
Permanent link to this record