scientific article; zbMATH DE number 1416629

Nemhauser, George I., Laurence A. Wolsey

Publication date: 19 March 2000

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

computational complexity matching duality relaxation submodular function valid inequalities discrete optimization separation facets polynomial-time algorithms basis 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 (only showing first 100 items - show all)

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

This page was built for publication: