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 cable trench problem: Combining the shortest path and minimum spanning tree problems, The multi-level uncapacitated facility location problem is not submodular, The shortest path problem with forbidden paths, Solving a fuzzy set-covering problem, ATM VP-based network design, 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, 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., 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., 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 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, 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., Consistency problems in ER-schemas for database systems, 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, Relocation problems arising in conservation biology, Valid integer polytope (VIP) penalties for branch-and-bound enumeration, 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, 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, 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, A Probabilistic Analysis of the K-Location Problem
