Fractional 0-1 programming and submodularity
From MaRDI portal
Abstract: In this note we study multiple-ratio fractional 0--1 programs, a broad class of NP-hard combinatorial optimization problems. In particular, under some relatively mild assumptions we provide a complete characterization of the conditions, which ensure that a single-ratio function is submodular. Then we illustrate our theoretical results with the assortment optimization and facility location problems, and discuss practical situations that guarantee submodularity in the considered application settings. In such cases, near-optimal solutions for multiple-ratio fractional 0--1 programs can be found via simple greedy algorithms.
Recommendations
Cites work
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- scientific article; zbMATH DE number 1302174 (Why is no real title available?)
- scientific article; zbMATH DE number 2190133 (Why is no real title available?)
- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
- A PTAS for capacitated sum-of-ratios optimization
- A branch-and-cut algorithm for the latent-class logit assortment problem
- A conic integer programming approach to stochastic joint location-inventory problems
- A global optimization algorithm for solving the minimum multiple ratio spanning tree problem
- A new saling algorithm for the maximum mean cut problem
- A note on maximizing a submodular set function subject to a knapsack constraint
- A primal-dual approximation algorithm for the facility location problem with submodular penalties
- A simple technique to improve linearized reformulations of fractional (hyperbolic) 0-1 programming problems
- An analysis of approximations for maximizing submodular set functions—I
- An exact method for assortment optimization under the nested logit model
- Assortment optimisation under a general discrete choice model: a tight analysis of revenue-ordered assortments
- Bandwidth packing with queuing delay costs: Bounding and heuristic solution procedures
- Boolean query optimization and the 0-1 hyperbolic sum problem
- Combinatorial Optimization with Rational Objective Functions
- Dynamic assortment optimization with a multinomial logit choice model and capacity constraint
- Exact approaches for competitive facility location with discrete attractiveness
- Exact solution of a class of nonlinear knapsack problems
- Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location
- Fractional 0-1 programming: applications and algorithms
- Fractional 0-1 programs: links between mixed-integer linear and conic quadratic formulations
- Global optimization of 0-1 hyperbolic programs
- Hyperbolic 0-1 programming and query optimization in information retrieval
- Improved approximation algorithms for the facility location problems with linear/submodular penalties
- Market Segmentation, Cannibalization, and the Timing of Product Introductions
- Maximizing a class of submodular utility functions
- Maximizing a class of utility functions over the vertices of a polytope
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing submodular set functions subject to multiple linear constraints
- Minimal ratio spanning trees
- On Solving Fractional (0, 1) Programs By Implicit Enumeration
- On complexity of unconstrained hyperbolic 0--1 programming problems
- On upper bounds for assortment optimization under the mixture of multinomial logit models
- Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
- Polymatroids and mean-risk minimization in discrete optimization
- Revenue Management Under a General Discrete Choice Model of Consumer Behavior
- Submodularity and local search approaches for maximum capture problems under generalized extreme value models
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- The maximum capture problem with random utilities: problem formulation and algorithms
- The maximum ratio clique problem
- The set covering problem with linear fractional functional
- The theory and practice of revenue management
- Tractable approximations for assortment planning with product costs
Cited in
(6)- Submodular maximization and its generalization through an intersection cut lens
- An exponential cone integer programming and piece-wise linear approximation approach for 0-1 fractional programming
- Fractional pebbling and thrifty branching programs
- Constrained assortment optimization under the mixed-logit model: approximation schemes and outer approximation approaches
- A Branch-and-Cut Algorithm for Submodular Interdiction Games
- Cutting planes for signomial programming
This page was built for publication: Fractional 0-1 programming and submodularity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2162513)
