scientific article

Nemhauser, George I., Laurence A. Wolsey

Publication date: 5 June 1993

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)

Order cones: a tool for deriving \(k\)-dimensional faces of cones of subfamilies of monotone games ⋮ On the complexity of sequentially lifting cover inequalities for the knapsack polytope ⋮ Routing of uncertain traffic demands ⋮ Extended formulations for the cardinality constrained subtree of a tree problem ⋮ A two-stage stochastic programming approach for project planning with uncertain activity durations ⋮ Genetic algorithms applied to the solution of hybrid optimal control problems in astrodynamics ⋮ Computing generating sets of lattice ideals and Markov bases of lattices ⋮ Efficient reformulation and solution of a nonlinear PDE-controlled flow network model ⋮ A cutting plane algorithm for the capacitated facility location problem ⋮ MIR closures of polyhedral sets ⋮ Lifting inequalities: a framework for generating strong cuts for nonlinear programs ⋮ The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm ⋮ Conic mixed-integer rounding cuts ⋮ Coefficient strengthening: a tool for reformulating mixed-integer programs ⋮ A generalization of column generation to accelerate convergence ⋮ Computing sparse and dense realizations of reaction kinetic systems ⋮ Cross-layer packet scheduling for downlink multiuser OFDM systems ⋮ On solving the Lagrangian dual of integer programs via an incremental approach ⋮ A FPTAS for a class of linear multiplicative problems ⋮ Polyhedral analysis for concentrator location problems ⋮ Solving the \(p\)-median problem with a semi-Lagrangian relaxation ⋮ On some geometry and equivalence classes of normal form games ⋮ Analysis of bounds for a capacitated single-item lot-sizing problem ⋮ Decision support system for mass dispensing of medications for infectious disease outbreaks and bioterrorist attacks ⋮ Polyhedral results on single node variable upper-bound flow models with allowed configurations ⋮ Hypergraphs and the Clar problem in hexagonal systems ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Lifting two-integer knapsack inequalities ⋮ Mixed-integer cuts from cyclic groups ⋮ On `informationally robust equilibria' for bimatrix games ⋮ In situ column generation for a cutting-stock problem ⋮ Two fast algorithms for all-pairs shortest paths ⋮ Space-aware ambients and processes ⋮ Optimizing over the first Chvátal closure ⋮ Pre-emptive scheduling problems with controllable processing times ⋮ Cyclic preference scheduling of nurses using a Lagrangian-based heuristic ⋮ A hybrid clustering algorithm ⋮ Static and dynamic source locations in undirected networks ⋮ The multiple traveling salesmen problem with moving targets ⋮ Sequence independent lifting for mixed knapsack problems with GUB constraints ⋮ Reverse split rank ⋮ On a class of subadditive duals for the uncapacitated facility location problem ⋮ Progress in presolving for mixed integer programming ⋮ Facets of the axial three-index assignment polytope ⋮ A survey of dynamic network flows ⋮ Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements ⋮ Global solution of optimization problems with signomial parts ⋮ Mathematical model for cyclic scheduling with work-in-process minimization ⋮ The mixing-MIR set with divisible capacities ⋮ Multi-item single source ordering problem with transportation cost: A Lagrangian decomposition approach ⋮ Boolean-controlled systems via receding horizon and linear programing ⋮ Lago: a (heuristic) branch and cut algorithm for nonconvex minlps ⋮ A multi-stop routing problem ⋮ Some observations about the extreme points of the generalized cardinality-constrained shortest path problem polytope ⋮ Benders decomposition for the uncapacitated multiple allocation hub location problem ⋮ Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method ⋮ A weighted even factor algorithm ⋮ Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes ⋮ How tight is the corner relaxation? ⋮ Computing robust basestock levels ⋮ Nonconvex, lower semicontinuous piecewise linear optimization ⋮ Production-process optimization algorithm: application to fed-batch bioprocess ⋮ Multi-level multi-item lot size planning with limited resources and general manufacturing structure. ⋮ The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times ⋮ A polynomial-time algorithm for computing the yolk in fixed dimension ⋮ On simple combinatorial optimization problems. A collection of contributions in honour of Jack van Lint ⋮ A mixed integer programming model for multiple stage adaptive testing ⋮ Polyhedral study of the capacitated vehicle routing problem ⋮ Testing balancedness and perfection of linear matrices ⋮ Forecast horizons and dynamic facility location planning ⋮ On cardinality constrained cycle and path polytopes ⋮ On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times ⋮ Ideal clutters ⋮ New Lagrangian relaxation based algorithm for resource scheduling with homogeneous subproblems ⋮ New bundle methods for solving Lagrangian relaxation dual problems ⋮ Adapting polyhedral properties from facility to hub location problems ⋮ Mixing polyhedra with two non divisible coefficients ⋮ Parallel Cholesky-based reduction for the weighted integer least squares problem ⋮ Inverse integer programming ⋮ Exact computational approaches to a stochastic uncapacitated single allocation \(p\)-hub center problem ⋮ Separating valid odd-cycle and odd-set inequalities for the multiple depot vehicle scheduling problem ⋮ Branch-and-cut approaches for chance-constrained formulations of reliable network design problems ⋮ The sparse signomial classification and regression model ⋮ A combinatorial optimization approach to the selection of statistical units ⋮ Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times ⋮ Large-scale 0-1 linear programming on distributed workstations ⋮ Quantitatively fair scheduling ⋮ A model for two-stage fixed charge transportation problem with multiple objectives and fuzzy linguistic preferences ⋮ A class of exponential neighbourhoods for the quadratic travelling salesman problem ⋮ Interior-point algorithms for global optimization ⋮ Models for planning capacity expansion in local access telecommunication networks ⋮ Multicriteria branch and bound: a vector maximization algorithm for mixed 0-1 multiple objective linear programming ⋮ Locating stops along bus or railway lines -- a bicriteria problem ⋮ Locating active sensors on traffic networks ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects ⋮ Logic-based modeling and solution of nonlinear discrete/continuous optimization problems ⋮ On compact formulations for integer programs solved by column generation ⋮ Integer-programming software systems ⋮ Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints ⋮ Solving planning and design problems in the process industry using mixed integer and global optimization

This page was built for publication: