Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
From MaRDI portal
Publication:3923934
DOI10.1016/S0304-0208(08)73471-6zbMATH Open0469.90052MaRDI QIDQ3923934FDOQ3923934
Authors: G. L. Nemhauser, Laurence A. Wolsey 
Publication date: 1981
Published in: North-Holland Mathematics Studies (Search for Journal in Brave)
branch-and-bound algorithmlocationlogisticsgreedy heuristicsmaximization of submodular functions0-1 quadratic programconstraint generation algorithm
Cited In (only showing first 100 items - show all)
- Robustness analysis of elementary flux modes generated by column generation
- Hub Location as the Minimization of a Supermodular Set Function
- On \(n\)-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets
- Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
- \((r|p)\)-centroid problems on networks with vertex and edge demand
- Pseudo-Boolean optimization
- A characterization of knapsacks with the max-flow--min-cut property
- Unimodularity of the Clar number problem
- Vehicle routing problem with trailers
- Tight linear programming relaxations of uncapacitated \(p\)-hub median problems
- Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
- GRASP for set packing problems.
- Preprocessing and cutting for multiple allocation hub location problems.
- Railway scheduling by network optimization
- Mathematical programming formulations for machine scheduling: A survey
- Generalized submodular cover problems and applications
- Vote trading in public elections
- Minimization of ordered, symmetric half-products
- New results on the completion time variance minimization
- Operations research in the space industry
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems
- A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem
- A survey of computational complexity results in systems and control
- Minimizing maximum indegree
- A dynamic convexized method for nonconvex mixed integer nonlinear programming
- An exact algorithm for the knapsack sharing problem with common items
- Individuals, populations and fluid approximations: a Petri net based perspective
- Activity nets: A guided tour through some recent developments
- Decomposition based hybrid metaheuristics
- A branch-price-and-cut algorithm for the minimum evolution problem
- A branch-price-and-cut method for the vegetable crop rotation scheduling problem with minimal plot sizes
- A branch-cut-and-price algorithm for the piecewise linear transportation problem
- The data transfer problem in a system of systems
- Multi-level facility location as the maximization of a submodular set function
- Deterministic network interdiction
- Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing
- Combinatorial optimization: current successes and directions for the future
- A column generation heuristic for a dynamic generalized assignment problem
- Optimization and analysis of the profitability of tariff structures with two-part tariffs
- An approximate dynamic programming approach for the vehicle routing problem with stochastic demands
- Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms
- Climate change and optimal energy technology R\&D policy
- A discrete dynamic convexized method for nonlinear integer programming
- Parametric mixed-integer 0-1 linear programming: The general case for a single parameter
- Properties of some ILP formulations of a class of partitioning problems
- The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem
- The multi-level uncapacitated facility location problem is not submodular
- Selection among ranked projects under segmentation, policy and logical constraints
- Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
- On separating cover inequalities for the multidimensional knapsack problem
- Using separation algorithms to generate mixed integer model reformulations
- Locating landfills--optimization vs. reality
- Approximation algorithms for knapsack problems with cardinality constraints
- Service network design in freight transportation
- Optimal project selection when borrowing and lending rates differ
- The shortest path problem with forbidden paths
- Maximization of submodular functions: theory and enumeration algorithms
- Mathematical models for selection of optimal place and size of connections considering the time-value of money
- On-line fault detection in discrete event systems by Petri nets and integer linear programming
- Fathoming rules for biobjective mixed integer linear programs: review and extensions
- The complexity of soft constraint satisfaction
- Unbounded knapsack problem: Dynamic programming revisited
- \(\varepsilon\)-approximation minimization of convex functions in fixed dimension
- A family of inequalities valid for the robust single machine scheduling polyhedron
- The transportation problem with exclusionary side constraints and two branch-and-bound algorithms
- Combinatorial optimization models for production scheduling in automated manufacturing systems
- A \(0-1\) goal programming model for scheduling multiple maintenance projects at a copper mine
- Relocation problems arising in conservation biology
- Pricing combinatorial auctions.
- Models for representing piecewise linear cost functions
- Exact computation of max weighted score estimators
- The simple plant location problem: Survey and synthesis
- A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
- The base-matroid and inverse combinatorial optimization problems.
- A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
- New convergent heuristics for 0-1 mixed integer programming
- Heuristic and exact algorithms for the max-min optimization of the multi-scenario knapsack problem
- Solving a capacitated hub location problem
- Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
- Formulations and exact algorithms for the vehicle routing problem with time windows
- Lagrangian duality applied to the vehicle routing problem with time windows
- A Probabilistic Analysis of the K-Location Problem
- A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
- Accelerating column generation for variable sized bin-packing problems
- An integrated cutting stock and sequencing problem
- Constraint-based optimization and utility elicitation using the minimax decision criterion
- An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem
- Production and inventory management under multiple resource constraints
- Solving a gas-lift optimization problem by dynamic programming
- Two-stage network constrained robust unit commitment problem
- Reliability redundancy allocation: an improved realization for nonconvex nonlinear programming problems
- An exact solution framework for the multiple gradual cover location problem
- Polymatroids and mean-risk minimization in discrete optimization
- Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
- Point of presence design in internet protocol networks with performance guarantees
- Coloring planar Toeplitz graphs and the stable set polytope.
- Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line
- Minimum fractional dominating functions and maximum fractional packing functions
- Polytopes related to interval vectors and incidence matrices
- An optimization framework for ``build-or-buy decisions in software architecture
This page was built for publication: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3923934)
