scientific article; zbMATH DE number 1416629

zbMath0944.90001MaRDI QIDQ4943600

Nemhauser, George I., Laurence A. Wolsey

Publication date: 19 March 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

computational complexitymatchingdualityrelaxationsubmodular functionvalid inequalitiesdiscrete optimizationseparationfacetspolynomial-time algorithmsbasis reduction

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Combinatorial aspects of matroids and geometric lattices (05B35) Polytopes and polyhedra (52Bxx)

Related Items

Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts, A Catalog of Formulations for the Network Pricing Problem, A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization, On Throughput Maximization Problem for UWB-Based Sensor Networks via Reformulation–Linearization Technique, Variants of Multi-resource Scheduling Problems with Equal Processing Times, Stochastic Learning Approach for Binary Optimization: Application to Bayesian Optimal Design of Experiments, Local Testing of Lattices, Crew Assignment with Duty Time Limits for Transport Services: Tight Multicommodity Models, Spatio-Temporal Pricing for Ridesharing Platforms, Modeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty Sets, Extreme Ray Feasibility Cuts for Unit Commitment with Uncertainty, A tutorial on the balanced minimum evolution problem, Unnamed Item, Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs, Analyzing read-once cutting plane proofs in Horn systems, Immersed NURBS for CFD Applications, Solving sparse principal component analysis with global support, Branch-and-bound solves random binary IPs in poly\((n)\)-time, Evaluating mixed-integer programming models over multiple right-hand sides, Constrained multi‐location assortment optimization under the multinomial logit model, Combining integer linear programming with a state‐of‐the‐art heuristic for the 2‐path network design problem, Convex geometry of Markovian Lindblad dynamics and witnessing non-Markovianity, On maximum ratio clique relaxations, An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents, Train stop scheduling problem: an exact approach using valid inequalities and polar duality, Minimum k‐cores and the k‐core polytope, Decision Diagrams for Discrete Optimization: A Survey of Recent Advances, A graph-based decomposition method for convex quadratic optimization with indicators, Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, Polyhedral results and stronger Lagrangean bounds for stable spanning trees, Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem, Adaptive solution prediction for combinatorial optimization, Feasible rounding based diving strategies in branch-and-bound methods for mixed-integer optimization, A theoretical and computational analysis of full strong-branching, Optimal Migration Planning of Telecommunication Equipment, Fair Policy Targeting, Lower bounds on the size of general branch-and-bound trees, Efficient enumeration of the optimal solutions to the correlation clustering problem, Behavioral analytics for myopic agents, Unit read-once refutations for systems of difference constraints, Optimization problems with evidential linear objective, Priority-based bin packing with subset constraints, Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation, Submodularity-based false data injection attack scheme in multi-agent dynamical systems, Learning lyapunov functions for hybrid systems, Node-based valid inequalities for the optimal transmission switching problem, Solving large-scale routing optimization problems with networks and only networks, Optimal Network Design with End-to-End Service Requirements, Network Reconstruction – A New Approach to the Traveling Salesman Problem and Complexity, On the multistage shortest path problem under distributional uncertainty, Integer set reduction for stochastic mixed-integer programming, Resolvability of Hamming Graphs, A Noncompact Formulation for Job-Shop Scheduling Problems in Traffic Management, Combining metaheuristics with mathematical programming, constraint programming and machine learning, The Directed Minimum Latency Problem, An Embarrassingly Parallel Method for Large-Scale Stochastic Programs, Polynomial time analysis of toroidal periodic graphs, How can we solve a linear Diophantine equation by the basis reduction algorithm, Deceptive Reinforcement Learning Under Adversarial Manipulations on Cost Signals, A Review for Submodular Optimization on Machine Scheduling Problems, Naval Wholesale Inventory Optimization, EXPLOITING OPTIMAL CONTROL FOR TARGET-ORIENTED MANIPULATION OF (BIO)CHEMICAL SYSTEMS: A MODEL-BASED APPROACH TO SPECIFIC MODIFICATION OF SELF-ORGANIZED DYNAMICS, Approximate and exact merging of knapsack constraints with cover inequalities, Optimization Methods: An Applications-Oriented Primer, On Tree-Constrained Matchings and Generalizations, How to Secure Matchings against Edge Failures, Unnamed Item, Two-Stage Stochastic Mixed-Integer Programs: Algorithms and Insights, Combining metaheuristics with mathematical programming, constraint programming and machine learning, Alternative Foldover Plans for Two-Level Nonregular Designs, Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints, Feasibility on using carbon credits: A multiobjective model, A hierarchical method for discrete structural topology design problems with local stress and displacement constraints, A Polyhedral Characterization of Border Bases, Continuum approximation techniques for the design of integrated package distribution systems, On Lagrangian Relaxation and Subset Selection Problems, Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information, Cutting to the Chase Solving Linear Integer Arithmetic, Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration, A DC Programming Approach for Mixed-Integer Linear Programs, Good Clusterings Have Large Volume, Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes, How to Secure Matchings Against Edge Failures, Rail schedule optimisation in the hunter valley coal chain, A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems, Outlier Detection in Time Series via Mixed-Integer Conic Quadratic Optimization, Unnamed Item, A genetic algorithm applied to optimal allocation in stratified sampling, Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems, Knapsack polytopes: a survey, Collaborative emergency berth scheduling based on decentralized decision and price mechanism, Algorithmic analysis of priority-based bin packing, Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem, On the copy complexity of width 3 Horn constraint systems, Effective methods for solving the bi-criteria \(p\)-center and \(p\)-dispersion problem, Mathematical models for on-line train calendars generation, The \(p\)-arborescence star problem: formulations and exact solution approaches, Computational approaches for zero forcing and related problems, Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming, Towards global bilevel dynamic optimization, Optimal length resolution refutations of difference constraint systems, Solving a \(k\)-node minimum label spanning arborescence problem to compress fingerprint templates, Global optimization of truss topology with discrete bar areas. II: Implementation and numerical results, Valid inequalities for the synchronization bus timetabling problem, Lagrangean relaxation of the hull-reformulation of linear generalized disjunctive programs and its use in disjunctive branch and bound, New formulations for the elementary shortest-path problem visiting a given set of nodes, Branch-and-cut for linear programs with overlapping SOS1 constraints, Surrogate-RLT cuts for zero-one integer programs, Convex hull characterizations of lexicographic orderings, A goal programming approach to vehicle routing problems with soft time windows, A trilevel programming approach for electric grid defense planning, Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem, Stage- and scenario-wise Fenchel decomposition for stochastic mixed 0-1 programs with special structure, A Benders decomposition algorithm for base station planning problem in WCDMA networks, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball, A pre-assignment heuristic algorithm for the master surgical schedule problem (MSSP), Truss topology optimization with discrete design variables -- guaranteed global optimality and benchmark examples, A Newton method for solving continuous multiple material minimum compliance problems, Lower and upper bounds for the spanning tree with minimum branch vertices, A computational study of a cutting plane algorithm for university course timetabling, Global optima for the Zhou-Rozvany problem, Two-stage stochastic lot-sizing problem under cost uncertainty, A survey of dual-feasible and superadditive functions, On a biobjective search problem in a line: formulations and algorithms, Exact algorithms for inventory constrained scheduling on a single machine, An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem, School choice with controlled choice constraints: hard bounds versus soft bounds, A military maintenance planning and scheduling problem, Information-theoretic approaches to branching in search, The value function of an infinite-horizon single-item lot-sizing problem, A branch-and-price approach for harvest scheduling subject to maximum area restrictions, Monoidal cut strengthening revisited, A hybrid branch-and-bound and evolutionary approach for allocating strings of applications to heterogeneous distributed computing systems, Stochastic robustness metric and its use for static resource allocations, Fitting piecewise linear continuous functions, Multiple UAV coalitions for a search and prosecute mission, Expressive markets for donating to charities, Ambiguous risk constraints with moment and unimodality information, A strengthened mixed-integer linear programming formulation for combined-cycle units, Liner shipping service scheduling and cargo allocation, Estimation of the number of iterations in integer programming algorithms using the regular partitions method, An optimization approach for planning daily drayage operations, Second-order cover inequalities, An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs, Solving the minimum label spanning tree problem by mathematical programming techniques, Optimal crop planting schedules and financial hedging strategies under ENSO-based climate forecasts, Preprocessing for a map sectorization problem by means of mathematical programming, A novel probabilistic formulation for locating and sizing emergency medical service stations, On a posterior evaluation of a simple greedy method for set packing, On dynamically generating relevant elementary flux modes in a metabolic network using optimization, Exact augmented Lagrangian duality for mixed integer linear programming, Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities, An exact method for a discrete multiobjective linear fractional optimization, Integer linear programming models for topology optimization in sheet metal design, A cross entropy-lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times, Variants of the \(\varepsilon\)-constraint method for biobjective integer programming problems: application to \(p\)-median-cover problems, Computing lower bounds on basket option prices by discretizing semi-infinite linear programming, Integer programming approach to static monopolies in graphs, Multi-period stochastic covering location problems: modeling framework and solution approach, Robust multicovers with budgeted uncertainty, Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs, Generation of networks with prescribed degree-dependent clustering, Mixed-integer programming techniques for decomposing IMRT fluence maps using rectangular apertures, Improved convergent heuristics for the 0-1 multidimensional knapsack problem, On the exact separation of mixed integer knapsack cuts, The directed orienteering problem, Mathematical model for efficient water flow management, Order selection in nonlinear time series models with application to the study of cell memory, On approximating optimal weight ``no-certificates in weighted difference constraint systems, Complementary column generation and bounding approaches for set partitioning formulations, Block-diagonal semidefinite programming hierarchies for 0/1 programming, Global solution of bilevel programs with a nonconvex inner program, Polytopes related to the \(l_{\infty}\)-distance between vectors, On column generation formulations for the RWA problem, An improved partial enumeration algorithm for integer programming problems, On the reformulation of topology optimization problems as linear or convex quadratic mixed 0-1 programs, Frequency assignment in mobile radio systems using branch-and-cut techniques, Optimization of order policies in supply networks, Fault tolerant sorting -- theoretical and empirical analyses of the randomized quickmergesort algorithm, A well-defined composite indicator: an application to corporate social responsibility, On the balanced minimum evolution polytope, A technique for speeding up the solution of the Lagrangean dual, Fast algorithms for the undirected negative cost cycle detection problem, Rapid prototyping of optimization algorithms using COIN-OR: a case study involving the cutting-stock problem, Projection, lifting and extended formulation integer and combinatorial optimization, Logical processing for integer programming, Airline crew scheduling: state-of-the-art, Multicriteria energy policy investments and energy market clearance via integer programming, The biobjective travelling purchaser problem, A simplicial branch and bound duality-bounds algorithm to linear multiplicative programming, Greedy approximations for minimum submodular cover with submodular cost, Set covering problem with conflict constraints, An elastic demand model for locating electric vehicle charging stations, Separation, dimension, and facet algorithms for node flow polyhedra, A cross entropy algorithm for the Knapsack problem with setups, Undecidability of restricted uniform recurrence equations, A logic-based Benders decomposition for microscopic railway timetable planning, A tight MIP formulation of the unit commitment problem with start-up and shut-down constraints, Variable neighbourhood decomposition search for \(0\)-\(1\) mixed integer programs, Evolutionary, constructive and hybrid procedures for the bi-objective set packing problem, Network models and biproportional rounding for fair seat allocations in the UK elections, Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems, An evolutionary algorithm based hyper-heuristic framework for the set packing problem, Application of a hybrid genetic algorithm to airline crew scheduling, Colorful edge decomposition of graphs: some polynomial cases, On Lagrangian relaxation for constrained maximization and reoptimization problems, Complexity of constrained sensor placement problems for optimal observability, Efficient computation of the Shapley value for large-scale linear production games, The sociotechnical teams formation problem: a mathematical optimization approach, Binary signed-graphic matroids: representations and recognition algorithms, Information coverage maximization for multiple products in social networks, Stochastic dual dynamic integer programming, A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints, The minimum chromatic violation problem: a polyhedral approach, A branch-and-cut algorithm for the generalized traveling salesman problem with time windows, Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs, Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm, Structural properties of affine sparsity constraints, Improved algorithms for optimal length resolution refutation in difference constraint systems, Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem, Computational risk management techniques for fixed charge network flow problems with uncertain arc failures, On generating maximal nondominated Benders cuts, A combinatorial algorithm for Horn programs, Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint, Balancing of agricultural census data by using discrete optimization, On a decision procedure for quantified linear programs, Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints, Dynamic pricing of flexible time slots for attended home delivery, Leveraged least trimmed absolute deviations, Determining closest targets on the extended facet production possibility set in data envelopment analysis: modeling and computational aspects, Alternative mathematical models and solution approaches for lot-sizing and scheduling problems in the brewery industry: analyzing two different situations, A math-heuristic Dantzig-Wolfe algorithm for capacitated lot sizing, Convex hull representation of the deterministic bipartite network interdiction problem, Spectral compressive sensing, A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables, Strong valid inequalities for fluence map optimization problem under dose-volume restrictions, A Davidson college multi-objective assignment problem: a case study, A Lagrangian approach for minimum cost single round robin tournaments, On tree-constrained matchings and generalizations, Cyclic and non-cyclic crew rostering problems in public bus transit, Analysis of a generalized linear ordering problem via integer programming, Network design formulations for scheduling U.S. air force channel route missions, An improved version of the augmented \(\varepsilon\)-constraint method (AUGMECON2) for finding the exact Pareto set in multi-objective integer programming problems, A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints, Polyhedral properties of the induced cluster subgraphs, Chvatal--Gomory--tier cuts for general integer programs, On the chance-constrained minimum spanning \(k\)-core problem, A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs, Air traffic flow management with layered workload constraints, Benders decomposition: solving binary master problems by enumeration, The multiple shortest path problem with path deconfliction, A Lagrangean-based heuristics for the target covering problem in wireless sensor network, The generalized minimum branch vertices problem: properties and polyhedral analysis, New product launch decisions with robust optimization, Retrieving a contingency table from a correspondence analysis solution, A polyhedral study of dynamic monopolies, Approximation schemes for \(r\)-weighted minimization knapsack problems, Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange, Optimization algorithms for the disjunctively constrained knapsack problem, A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices, A solution framework for linear PDE-constrained mixed-integer problems, D-optimal design for network A/B testing, Analyzing unit read-once refutations in difference constraint systems, On convergence of scatter search and star paths with directional rounding for 0--1 mixed integer programs, Parallel execution of schedules with random dependency graph, Exact and heuristic algorithms for the maximum weighted submatrix coverage problem, The Lagrangian, constraint qualifications and economics, Exact computation of censored least absolute deviations estimator, Cost-oriented assembly line balancing: model formulations, solution difficulty, upper and lower bounds, An exact projection-based algorithm for bilevel mixed-integer problems with nonlinearities, Hierarchical solution of non-convex optimal control problems with application to autonomous driving, On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations, Kantorovich-Rubinstein distance and barycenter for finitely supported measures: foundations and algorithms, A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming, Graph coloring inequalities from all-different systems, Parsimonious binary-encoding in integer programming, Revealed preference tests for weak separability: an integer programming approach, Exact approaches for the minimum subgraph diameter problem, Cutting to the chase., Handling least privilege problem and role mining in RBAC, On the exact separation of cover inequalities of maximum-depth, A column generation mathematical programming approach for a class-faculty assignment problem with preferences, Substitution-based equipment balancing in service networks with multiple equipment types, Probability chains: a general linearization technique for modeling reliability in facility location and related problems, New insights on integer-programming models for the kidney exchange problem, Stochastic Lipschitz dynamic programming, Assessing the effectiveness of \(k\)-shortest path sets in problems of network interdiction