Submodularity and local search approaches for maximum capture problems under generalized extreme value models

DOI10.1016/J.EJOR.2021.09.006zbMATH Open1506.90136arXiv2102.05754OpenAlexW3199535320WikidataQ114184421 ScholiaQ114184421MaRDI QIDQ2116913FDOQ2116913

Authors: Tien Thanh Dam, Thuy Anh Ta, Tien Mai 

Publication date: 18 March 2022

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: We study the maximum capture problem in facility location under random utility models, i.e., the problem of seeking to locate new facilities in a competitive market such that the captured user demand is maximized, assuming that each customer chooses among all available facilities according to a random utility maximization model. We employ the generalized extreme value (GEV) family of discrete choice models and show that the objective function in this context is monotonic and submodular. This finding implies that a simple greed heuristic can always guarantee an (1-1/e) approximation solution. We further develop a new algorithm combining a greedy heuristic, a gradient-based local search and an exchanging procedure to efficiently solve the problem. We conduct experiments using instances of difference sizes and under different discrete choice models, and we show that our approach significantly outperforms prior approaches in terms of both returned objective value and CPU time. Our algorithm and theoretical findings can be applied to the maximum capture problems under various random utility models in the literature, including the popular multinomial logit, nested logit, cross nested logit, and the mixed logit models.

Full work available at URL: https://arxiv.org/abs/2102.05754

Recommendations

• The maximum capture problem with random utilities: problem formulation and algorithms
• Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
• A branch-and-bound algorithm for the maximum capture problem with random utilities
• A multicut outer-approximation approach for competitive facility location under random utilities
• The maximum capture problem with heterogeneous customers

zbMATH Keywords

facilities planning and designgreedy heuristicmaximum capturerandom utility maximizationgeneralized extreme value

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Cites Work

• Discrete Choice Methods with Simulation
• Trust Region Methods
• An algorithmic framework for convex mixed integer nonlinear programs
• An outer-approximation algorithm for a class of mixed-integer nonlinear programs
• Title not available (Why is that?)
• Competitive facility location and design problem
• Title not available (Why is that?)
• An analysis of approximations for maximizing submodular set functions—I
• Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
• The maximum capture problem with random utilities: problem formulation and algorithms
• The impact of client choice on preventive healthcare facility network design
• A Discrete Choice Model for Ordered Alternatives
• Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
• Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
• An approximation algorithm for a competitive facility location problem with network effects
• Branch-and-cut approach based on generalized Benders decomposition for facility location with limited choice rule
• A multicut outer-approximation approach for competitive facility location under random utilities
• Generalized Benders decomposition for competitive facility location with concave demand and zone-specialized variable attractiveness

Cited In (8)

• Store location with multipurpose shopping trips and a new random utility customers' choice model
• Joint location and cost planning in maximum capture facility location under random utilities
• Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint
• Sequential customers' decisions in facility location with comparison-shopping
• The follower competitive facility location problem under the nested logit choice rule
• Fractional 0-1 programming and submodularity
• The maximum capture problem with heterogeneous customers
• The maximum capture problem with random utilities: problem formulation and algorithms

Uses Software

• Bonmin

This page was built for publication: Submodularity and local search approaches for maximum capture problems under generalized extreme value models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2116913)