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
(12)- The follower competitive facility location problem under the nested logit choice rule
- Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
- Fractional 0-1 programming and submodularity
- Improved approximation algorithms for \(k\)-submodular maximization under a knapsack constraint
- Sequential customers' decisions in facility location with comparison-shopping
- The maximum capture problem with heterogeneous customers
- A multicut outer-approximation approach for competitive facility location under random utilities
- A branch-and-bound algorithm for the maximum capture problem with random utilities
- The maximum capture problem with random utilities: problem formulation and algorithms
- 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
- Joint location and cost planning in maximum capture facility location under random utilities
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)
