Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
North-Holland mathematics studiesPublished 1 January 1981
George L. Nemhauser, Laurence A. Wolsey
Citations136
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A constraint generation algorithm and a branch-and-bound algorithm that uses linear programming relaxations that uses greedy heuristics to produce feasible solutions, which, in turn, are used to generate upper bounds.
Abstract
We consider integer programming formulations of problems that involve the maximization of submodular functions. A location problem and a 0–1 quadratic program are well-known special cases. We give a constraint generation algorithm and a branch-and-bound algorithm that uses linear programming relaxations. These algorithms are familiar ones except for their particular selections of starting constraints, subproblems and partitioning rules. The algorithms use greedy heuristics to produce feasible solutions, which, in turn, are used to generate upper bounds. The novel features of the algorithms are the performance guarantees they provide on the ratio of lower to upper bounds on the optimal value.
Keywords
Computer Science
Mathematical ProgrammingAn analysis of approximations for maximizing submodular set functions—I
4,458 Citations1978George L. Nemhauser, Laurence A. Wolsey +1 more
It is shown that a “greedy” heuristic always produces a solution whose value is at least 1 −[(K − 1/K]K times the optimal value, which can be achieved for eachK and has a limiting value of (e − 1)/e, where e is the base of the natural logarithm.
Journal of the Operations Research Society of AmericaSolution of a Large-Scale Traveling-Salesman Problem
1,314 Citations1954George B. Dantzig, R. Fulkerson +1 more
International series in management science/operations research/International series in operations research & management scienceMulticommodity Distribution System Design by Benders Decomposition * † ‡
983 Citations2010Arthur M. Geoffrion, G. W. Graves§
Management ScienceMulticommodity Distribution System Design by Benders Decomposition
901 Citations1974Arthur M. Geoffrion, Glenn W. Graves
Management ScienceExceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
802 Citations1977Gérard Cornuéjols, Marshall L. Fisher +1 more
Management ScienceImproved Linear Integer Programming Formulations of Nonlinear Integer Problems
766 Citations1975Fred Glover
Operations ResearchAccelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
722 Citations1981Thomas L. Magnanti, Richard T. Wong
A new technique for accelerating the convergence of the algorithm and theory for distinguishing “good” model formulations of a problem that has distinct but equivalent mixed integer programming representations is introduced.
Mathematics of Operations ResearchBest Algorithms for Approximating the Maximum of a Submodular Set Function
556 Citations1978George L. Nemhauser, Laurence A. Wolsey
This work presents a family of algorithms that involve the partial enumeration of all sets of cardinality q and then a greedy selection of the remaining elements, q = 0,..., K-1.
Management ScienceNote—On “Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms”
438 Citations1979Gérard Cornuéjols, Marshall L. Fisher +1 more
In the course of the deliberations of the 1977 Lanchester Prize Committee, Alan J. Goldman brought to the authors' attention an error in the proof of Lemma 1 of their paper, which is true and the original correct, but long and intricate, proof was provided.
European Journal of Operational ResearchAn algorithm for the quadratic assignment problem using Bender's decomposition
171 Citations1978L. Kaufman, F. Broeckx
The mixed integer program obtained by Glover's method is discussed and a solution using Bender's decomposition is proposed.
Operations ResearchDirect Search Algorithms for Zero-One and Mixed-Integer Programming
110 Citations1967C. E. Lemke, Kurt Spielberg
A method of solution for the mixed integer-programming problem is proposed, based on an exhaustive search of the integer variables, coupled with an efficient use of the product form of the basis matrix inverse, for the linear programming calculations.
Mathematical programming studiesExperiments in the formulation of integer programming problems
106 Citations1974Hugh Williams
The purpose of this paper is to investigate the computational effects of different formulations on such problems as a market allocation problem, a combinatorial problem, two mining problems and a problem of logical design.
Annals of discrete mathematicsComputer Codes for Problems of Integer Programming
75 Citations1979A. H. Land, Susan Powell
This chapter presents a “consumer research” report on the different products and also the methods for solving pure integer problems—frequently with special combinatorial structures.
SIAM Journal on Algebraic and Discrete MethodsA Canonical Representation of Simple Plant Location Problems and Its Applications
61 Citations1980Gérard Cornuéjols, George L. Nemhauser +1 more
A constructive proof that a set function w is a simple location function if and only if it can be represented in the canonical form $w ( S ) = r_\emptyset + \Sigma _{T \cap S \ne \emptYSet } r_T $ with $r_T \geqq 0$ for all $\emptys set T \subset N$.
Operations ResearchWorst-Case and Probabilistic Analysis of Algorithms for a Location Problem
47 Citations1980Gérard Cornuéjols, George L. Nemhauser +1 more
If n is suitably large and K is fixed or does not grow too rapidly with n, the K vertices of largest degree nearly always constitute an optimal solution.
Annals of discrete mathematicsAlgorithms for Exploiting the Structure of the Simple Plant Location Problem
30 Citations1977Monique Guignard, Kurt Spielberg
A number of approaches to the important simple plant location problem are described, including modified simplex methods which exploit triangular bases and several decomposition approaches.
Annals of discrete mathematicsHow Can Specialized Discrete and Convex Optimization Methods Be Married?
10 Citations1977Arthur M. Geoffrion
The question of how the two specialized types of algorithms can be married to provide an effective overall approach to the problem is raised.