Submodularity and local search approaches for maximum capture problems under generalized extreme value models
From MaRDI portal
(Redirected from Publication:2116913)
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.
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
Cites work
- scientific article; zbMATH DE number 3965301 (Why is no real title available?)
- scientific article; zbMATH DE number 1559542 (Why is no real title available?)
- A Discrete Choice Model for Ordered Alternatives
- A multicut outer-approximation approach for competitive facility location under random utilities
- An algorithmic framework for convex mixed integer nonlinear programs
- An analysis of approximations for maximizing submodular set functions—I
- An approximation algorithm for a competitive facility location problem with network effects
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- Branch-and-cut approach based on generalized Benders decomposition for facility location with limited choice rule
- Competitive facility location and design problem
- Discrete Choice Methods with Simulation
- Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
- Generalized Benders decomposition for competitive facility location with concave demand and zone-specialized variable attractiveness
- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location Problem
- Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
- The impact of client choice on preventive healthcare facility network design
- The maximum capture problem with random utilities: problem formulation and algorithms
- Trust Region Methods
Cited in
(15)- Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
- Store location with multipurpose shopping trips and a new random utility customers' choice model
- Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
- Joint location and cost planning in maximum capture facility location under random utilities
- An efficient branch-and-cut approach for large-scale competitive facility location problems with limited choice rule
- A multicut outer-approximation approach for competitive 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
- Constrained assortment optimization under the mixed-logit model: approximation schemes and outer approximation approaches
- A branch-and-bound algorithm for the maximum capture problem with random utilities
- The follower competitive facility location problem under the nested logit choice rule
- Fractional 0-1 programming and submodularity
- Maximum capture location problem with random utilities and overflow penalties
- The maximum capture problem with heterogeneous customers
- The maximum capture problem with random utilities: problem formulation and algorithms
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)
