Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
From MaRDI portal
Publication:3923934
DOI10.1016/S0304-0208(08)73471-6zbMath0469.90052MaRDI QIDQ3923934
Nemhauser, George I., Laurence A. Wolsey
Publication date: 1981
Published in: North-Holland Mathematics Studies (Search for Journal in Brave)
branch-and-bound algorithm; location; logistics; greedy heuristics; maximization of submodular functions; 0-1 quadratic program; constraint generation algorithm
Related Items
The shortest path problem with forbidden paths, Robustness analysis of elementary flux modes generated by column generation, Exact computation of max weighted score estimators, Individuals, populations and fluid approximations: a Petri net based perspective, Decomposition based hybrid metaheuristics, The data transfer problem in a system of systems, 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, Multi-level facility location as the maximization of a submodular set function, Models and algorithms for network reduction, Obtaining cell counts for contingency tables from rounded conditional frequencies, The weighted uncapacitated planned maintenance problem: complexity and polyhedral properties, Lifted Euclidean inequalities for the integer single node flow set with upper bounds, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, Strengthening the reliability fixed-charge location model using clique constraints, \((r|p)\)-centroid problems on networks with vertex and edge demand, Algorithms and implementation of a set partitioning approach for modular machining line design, Nodes selection strategy in cooperative tracking problem, Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty, New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints, On \(n\)-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets, Sell or hold: A simple two-stage stochastic combinatorial optimization problem, Mixed-integer linear optimization for optimal lift-gas allocation with well-separator routing, Operations research in the space industry, A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem, A flexible ILP formulation for hierarchical clustering, A column generation based algorithm for the robust graph coloring problem, Upper bounds and heuristics for the 2-club problem, Optimization models for targeted offers in direct marketing: exact and heuristic algorithms, Climate change and optimal energy technology R\&D policy, A dynamic convexized method for nonconvex mixed integer nonlinear programming, Video distribution under multiple constraints, Solving a fuzzy set-covering problem, An exact penalty function approach for nonlinear integer programming problems, ATM VP-based network design, Size-constrained graph partitioning polytopes, Stochastic lot-sizing problem with deterministic demands and Wagner-Whitin costs, On a class of mixed-integer sets with a single integer variable, A primogenitary linked quad tree approach for solution storage and retrieval in heuristic binary optimization, Buyer-supplier games: optimization over the core, Graph coloring with rejection, Polytopes related to interval vectors and incidence matrices, Lifting cover inequalities for the precedence-constrained knapsack problem, Resolution search, Solving sequential knapsack problems, Non-standard approaches to integer programming, Pseudo-Boolean optimization, Cutting planes in integer and mixed integer programming, An LP-based proof for the non-existence of a pair of orthogonal Latin squares of order 6., A greedy approximation for minimum connected dominating sets, New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints, Stochastic set packing problem, Differential approximation schemes for half-product related functions and their scheduling applications, Approximability issues for unconstrained and constrained maximization of half-product related functions, Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints, Optimal control on a graph with application to train scheduling problems, Railway scheduling by network optimization, Mathematical programming formulations for machine scheduling: A survey, A comparison of heuristics and relaxations for the capacitated plant location problem, The multiple depot, multiple traveling salesmen facility-location problem: Vehicle range, service frequency, and heuristic implementations, A sensitivity analysis of matching coin game strategies, An alternative formulation for certain fuzzy set-covering problems, Upper and lower bounding strategies for the generalized minimum spanning tree problem, Performance guarantees of a greedy algorithm for minimizing a supermodular set function on comatroid, An exact algorithm for the knapsack sharing problem with common items, A partial enumeration algorithm for pure nonlinear integer programming, Improving computational capabilities for addressing volume constraints in forest harvest scheduling problems, Vote trading in public elections, On separating cover inequalities for the multidimensional knapsack problem, A heuristic genetic algorithm for product portfolio planning, Exact algorithms for procurement problems under a total quantity discount structure, Unimodularity of the Clar number problem, Locating landfills--optimization vs. reality, Lower bounds for the two-stage uncapacitated facility location problem, Multiprogramming genetic algorithm for optimization problems with permutation property, A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing, The stable set polytope of icosahedral graphs, A computationally efficient robust tube based MPC for linear switched systems, Lifting facets of the cut polytope, A note on the MIR closure, Bounds on the size of branch-and-bound proofs for integer knapsacks, Decomposition schemes and acceleration techniques in application to production-assembly-distribution system design, Lagrangian approaches for a class of matching problems in computational biology, Goal programming in the context of the assignment problem and a computationally effective solution method, Complexity of local search for the \(p\)-median problem, Solving the car sequencing problem via branch \& bound, A discrete dynamic convexized method for nonlinear integer programming, Polymatroids and mean-risk minimization in discrete optimization, Parametric mixed-integer 0-1 linear programming: The general case for a single parameter, Facets of the \((s,t)-p\)-path polytope, Mathematical models for optimal usage of tributary cards in wavelength assignment for DWDM ring networks, Cutting plane algorithms for \(0-1\) programming based on cardinality cuts, Optimization and analysis of the profitability of tariff structures with two-part tariffs, Conley's spectral sequence via the sweeping algorithm, A column generation heuristic for a dynamic generalized assignment problem, Scheduling of corrugated paper production, A primal-dual algorithm for the economic lot-sizing problem with multi-mode replenishment, A compact formulation of the ring loading problem with integer demand splitting, Cutting plane algorithms for the inverse mixed integer linear programming problem, Minimum fractional dominating functions and maximum fractional packing functions, A discrete mechanics approach to dislocation dynamics in BCC crystals, An approximate dynamic programming approach for the vehicle routing problem with stochastic demands, Maximization of submodular functions: theory and enumeration algorithms, A notion of cross-perfect bipartite graphs, Decomposition, reformulation, and diving in university course timetabling, Knapsack problems with setups, Non-linear anonymous pricing combinatorial auctions, An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem, Solving multiobjective, multiconstraint knapsack problems using mathematical programming and evolutionary algorithms, Mathematical models for selection of optimal place and size of connections considering the time-value of money, On the representability of totally unimodular matrices on bidirected graphs, On-line fault detection in discrete event systems by Petri nets and integer linear programming, A fixed interval due-date scheduling problem with earliness and due-date costs, An intelligent interactive project management support system, An algorithm for solving quadratic network flow problems, Using separation algorithms to generate mixed integer model reformulations, Two algorithms for maximizing a separable concave function over a polymatroid feasible region, Improved complexity bounds for location problems on the real line, A polyhedral approach to edge coloring, A counterexample to a question of Merikoski and Virtanen on the compounds of unitary matrices, Vehicle crew scheduling to complete specific tasks and bulk-tasks at depots, A graph-theoretic heuristic for designing loop-layout manufacturing systems, A characterization of knapsacks with the max-flow--min-cut property, Complexity of the closest vector problem in a lattice generated by a (0,1)-matrix, On the convex hull of feasible solutions to certain combinatorial problems, Lot-sizing polyhedra with a cardinality constraint, On tightening cover induced inequalities, Neural network methods in combinatorial optimization, A stochastic neural network for resource constrained scheduling, Vehicle routing problem with trailers, Properties of some ILP formulations of a class of partitioning problems, A relation between the knapsack and group knapsack problems, Adjacency on the constrained assignment problem, Process planning in a fuzzy environment, Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, A robustness approach to uncapacitated network design problems, Tight linear programming relaxations of uncapacitated \(p\)-hub median problems, An extended formulation approach to the edge-weighted maximal clique problem, Reducing depot-related costs of large bus operators. A case study in Bangkok, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Optimizing nuclear power plant refueling with mixed-integer programming, Multi-objective optimization over convex disjunctive feasible sets using reference points, Combinatorial optimization models for production scheduling in automated manufacturing systems, A cutting-plane approach to mixed 0-1 stochastic integer programs, The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem, Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks, The complexity of multidimensional periodic scheduling, Minimal connected enclosures on an embedded planar graph, Nonlinear integer programming by Darwin and Boltzmann mixed strategy, A lexicographic approach to bi-objective loading of a flexible assembly system, Solving the generalised assignment problem using polyhedral results, HOP: A software tool for production scheduling at Bridgestone/Firestone Off-The-Road, Economic spare capacity planning for DCS mesh-restorable networks, A linear and discrete programming framework for representing qualitative knowledge, Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times, An exact algorithm for the constraint satisfaction problem: Application to logical inference, Directed Steiner problems with connectivity constraints, Experiments with parallel branch-and-bound algorithms for the set covering problem, Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems, Investment planning for urban roads, Collapsing and lifting for the cut cone, Balancing problems in acyclic networks, A \(0-1\) goal programming model for scheduling multiple maintenance projects at a copper mine, MINTO, a Mixed INTeger Optimizer, Polyhedral structure and properties of a model for layout design, An algorithm for the planar three-index assignment problem, Geometric comparison of combinatorial polytopes, A column generation approach to job grouping for flexible manufacturing systems, Some applications of nonnegative linear systems: Farkas strikes again, Partitioning of sequentially ordered systems using linear programming, Distributed processing of divisible jobs with communication startup costs, The \(k\)-cardinality assignment problem, An efficient algorithm for a capacitated subtree of a tree problem in local access telecommunication networks, Channel allocation in cellular radio networks, On dominated terms in the general knapsack problem, Cardinality constrained Boolean quadratic polytope, A binary integer linear program with multi-criteria and multi-constraint levels, Solution methods for the balancing of jet turbines, A model for the capacitated \(p\)-facility location problem in global environments, Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem, Complexity of searching an immobile hider in a graph, Polyhedral characterizations and perfection of line graphs, The inverse-parametric knapsack problem, Activity nets: A guided tour through some recent developments, A special class parametric of knapsack problems: Analytic aids and heuristics, The design of a 0-1 integer optimizer and its application in the Carmen system, \(k\)-interchange heuristic as an optimization procedure for material handling applications, Material compatibility constraints for make-to-order production planning., Foundation-penalty cuts for mixed-integer programs., Integer programming, Barvinok's counting algorithm and Gomory relaxations., Designing communication networks for distributed control agents., GRASP for set packing problems., Loading and scheduling of a flexible assembly system by mixed integer programming., Pricing combinatorial auctions., Mathematical models for applying cell suppression methodology in statistical data protection., On polynomial complexity of a stochastic algorithm for mixed zero-one programs., Using penalty function and tabu search to solve cell formation problems with fixed cell cost., Coloring planar Toeplitz graphs and the stable set polytope., Cutting planes from a mixed integer Farkas lemma., Preprocessing and cutting for multiple allocation hub location problems., Multi-objective design of team oriented assembly systems., On the directed hop-constrained shortest path problem, Models for representing piecewise linear cost functions, Approximation algorithms for knapsack problems with cardinality constraints, Unbounded knapsack problem: Dynamic programming revisited, The asymmetric traveling salesman problem with replenishment arcs, An improved approximation algorithm of MULTIWAY CUT., Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands, Service network design in freight transportation, A multi-depot pickup and delivery problem with a single hub and heterogeneous vehicles, A Lagrangian relax-and-cut approach for the two-stage capacitated facility location problem, Valid inequalities for a class of assembly system problems, Using DEA to obtain efficient solutions for multi-objective 0--1 linear programs, Generalized submodular cover problems and applications, A network-flow-based lower bound for the minimum weighted integer coloring problem, Combinatorial optimization: current successes and directions for the future, Simultaneous loading, routing, and assembly plan selection in a flexible assembly system, Optimal project selection when borrowing and lending rates differ, A theory of complexity for continuous time systems, On the linear description of the 3-cycle polytope, Erratum to ``Comparison of column generation models for channel assignment in cellular networks, A model and methodologies for the location problem with logistical components, Totally tight Chvatal-Gomory cuts, Strengthening Chvátal-Gomory cuts and Gomory fractional cuts, A branch-and-cut algorithm for the minimum branch vertices spanning tree problem, Short rational generating functions for solving some families of fuzzy integer programming problems, Maximum coverage problem with group budget constraints, A two-stage stochastic programming approach for multi-activity tour scheduling, Container shipping service selection and cargo routing with transshipment limits, A two-stage stochastic programming approach for influence maximization in social networks, Valid inequalities for the single arc design problem with set-ups, Local search inequalities, Multi-commodity variable upper bound flow models, Fathoming rules for biobjective mixed integer linear programs: review and extensions, Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes, Facets for continuous multi-mixing set with general coefficients and bounded integer variables, Outer approximation and submodular cuts for maximum capture facility location problems with random utilities, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, Multicommodity flows and Benders decomposition for restricted continuous location problems, A generalized Benders decomposition based algorithm for an inventory location problem with stochastic inventory capacity constraints, Two-echelon, multi-commodity supply chain network design with mode selection, lead-times and inventory costs, A class of web-based facets for the generalized vertex packing problem, Minimization of ordered, symmetric half-products, A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem, A provable better Branch and Bound method for a nonconvex integer quadratic programming problem, Applying the minimax criterion in stochastic recourse programs, Partial convexification cuts for 0--1 mixed-integer programs, An improved Lagrangian relaxation and dual ascent approach to facility location problems, A probabilistic analysis of the maximal covering location problem, A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems, Note on combinatorial optimization with max-linear objective functions, Efficient reformulation for 0-1 programs -- methods and computational results, A branch-and-bound method for multicommodity location with balancing requirements, Deterministic network interdiction, On the minors of an incidence matrix and Smith normal form, New results on the completion time variance minimization, The base-matroid and inverse combinatorial optimization problems., A generalized dual phase-2 simplex algorithm., An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope., A computational study of using preprocessing and stronger formulations to solve large general fixed charge problems, Consistency problems in ER-schemas for database systems, The simple plant location problem: Survey and synthesis, A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths, The maximum capture problem with random utilities: problem formulation and algorithms, The transportation problem with exclusionary side constraints and two branch-and-bound algorithms, A search heuristic for the sequence-dependent economic lot scheduling problem, Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line, Covering non-uniform hypergraphs, Graph imperfection. I, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Two alternative models for farm management: Discrete versus continuous time horizon, Stock selection heuristics for interdependent items, Discrete models for data imputation, Polynomial approximation schemes and exact algorithms for optimum curve segmentation problems, A column generation approach to the coalition formation problem in multi-agent systems, Hybrid genetic algorithm for optimization problems with permutation property, Minimizing maximum indegree, Efficient solution generation for multiple objective linear programming based on extreme ray generation method, Monge matrices make maximization manageable, Batch scheduling to minimize total completion time, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, Permuting matrices to avoid forbidden submatrices, The application of valid inequalities to the multi-stage lot-sizing problem, A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization, Cardinality-restricted chains and antichains in partially ordered sets, The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs, Tighter representations for set partitioning problems, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, On solving the continuous data editing problem, Some heuristic methods for solving \(p\)-median problems with a coverage constraint, Real-time freight locomotive rescheduling and uncovered train detection during disruption, A simple finite cutting plane algorithm for integer programs, Relocation problems arising in conservation biology, Valid integer polytope (VIP) penalties for branch-and-bound enumeration, An exact solution framework for the multiple gradual cover location problem, Large-scale influence maximization via maximal covering location, Pareto optimization for subset selection with dynamic cost constraints, An exact cutting plane method for \(k\)-submodular function maximization, Probabilistic Partial Set Covering with an Oracle for Chance Constraints, ParaXpress: an experimental extension of the FICO Xpress-Optimizer to solve hard MIPs on supercomputers, A framework for solving mixed-integer semidefinite programs, Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location, Optimal matrix-segmentation by rectangles, A survey of computational complexity results in systems and control, Computing an integer point of a simplex with an arbitrary starting homotopy-like simplicial algorithm, Branch and cut methods for network optimization, An approximate algorithm for nonlinear integer programming, An approximate algorithm for nonlinear integer programming, The multi-level uncapacitated facility location problem is not submodular, On mixed-integer zero-one representations for separable lower-semicontinuous piecewise-linear functions, Facets of the \(p\)-cycle polytope, Comparison of column generation models for channel assignment in cellular networks, A method of transferring polyhedron between the intersection-form and the sum-form, A polynomially solvable special case of the unbounded knapsack problem, A branch-and-price algorithm for the Steiner tree packing problem., The cable trench problem: Combining the shortest path and minimum spanning tree problems, The multi-level uncapacitated facility location problem is not submodular, The follower competitive facility location problem under the nested logit choice rule, Submodular function minimization and polarity, An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions, A family of inequalities valid for the robust single machine scheduling polyhedron, A dual simplex algorithm for the canonical representation of the uncapacitated facility location problem, Feasibility checking in Horn constraint systems through a reduction based approach, The minimum flow cost Hamiltonian cycle problem: a comparison of formulations, Broadcasting in unstructured peer-to-peer overlay networks, On the adjustment problem for linear programs, Adaptive modeling, adaptive data assimilation and adaptive sampling, A pegging approach to the precedence-constrained knapsack problem, New convergent heuristics for 0-1 mixed integer programming, Optimal multicast route packing, Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Solving a capacitated hub location problem, Point of presence design in internet protocol networks with performance guarantees, Supermodular functions and the complexity of MAX CSP, A polyhedral approach for a constrained quadratic 0-1 problem, Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions, Selection among ranked projects under segmentation, policy and logical constraints, A dynamic model of controlling invasive species, Modeling and solving a crew assignment problem in air transportation, Seasonal clustering technique for time series data, Redesigning a warehouse network, Polyhedral results for the bipartite induced subgraph problem, A mixed R{\&}D projects and securities portfolio selection model, Out of order quantifier elimination for standard quantified linear programs, Multi-period capacitated location with modular equipments, The complexity of soft constraint satisfaction, Constraint-based optimization and utility elicitation using the minimax decision criterion, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs, Heuristic and exact algorithms for the max-min optimization of the multi-scenario knapsack problem, How to allocate hard candies fairly, A mathematical programming approach to key-based election analysis, Constrained 0-1 quadratic programming: basic approaches and extensions, An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem, Optimization with binet matrices, A multiple server location-allocation model for service system design, Formulations and exact algorithms for the vehicle routing problem with time windows, Rerouting tunnels for MPLS network resource optimization, Balancedness of edge covering games, Integer programming approach to reactive scheduling in make-to-order manufacturing, Classification of orthogonal arrays by integer programming, Production and inventory management under multiple resource constraints, An optimization framework for ``build-or-buy decisions in software architecture, Exact solution procedures for the balanced unidirectional cyclic layout problem, Beam search heuristic to solve stochastic integer problems under probabilistic constraints, Integer programming approach to production scheduling for make-to-order manufacturing, Approximation algorithms for the Euclidean bipartite TSP, Generation of classes of robust periodic railway timetables, Best compromise solution for a new multiobjective scheduling problem, A new filled function method for nonlinear integer programming problem, Lagrangian duality applied to the vehicle routing problem with time windows, Exact solutions to a class of stochastic generalized assignment problems, Solving a gas-lift optimization problem by dynamic programming, Two-stage network constrained robust unit commitment problem, Comparative approaches to equipment scheduling in high volume factories, The average shadow price for MILPs with integral resource availability and its relationship to the marginal unit shadow price, A multi-period machine assignment problem, Optimization and reconstruction of \(hv\)-convex (0,1)-matrices, Orthogonal drawings of graphs with vertex and edge labels, Reliability redundancy allocation: an improved realization for nonconvex nonlinear programming problems, A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, Equivalence of some LP-based lower bounds for the Golomb ruler problem, Improved approximation of maximum vertex cover, Assignment of swimmers to dual meet events, Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics, Container vessel scheduling with bi-directional flows, Accelerating column generation for variable sized bin-packing problems, An integrated cutting stock and sequencing problem, Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems, A polyhedral approach to bisubmodular function minimization, On additive approximate submodularity, Interactive optimization of submodular functions under matroid constraints, Hub Location as the Minimization of a Supermodular Set Function, Tight Approximation Bounds for the Seminar Assignment Problem, A Probabilistic Analysis of the K-Location Problem
