scientific article; zbMATH DE number 193499
Benders' decompositioncomputabilitycutting methodsexact and nonexact algorithmsgreedyheuristic proceduresLagrangian dual ideaslocal searchmatroidsnonpolynomial algorithmspartial enumerationtime complexitytime-polynomial algorithmstruncated exponential algorithmsworst-case analysis
Combinatorial aspects of matroids and geometric lattices (05B35) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68Rxx) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Linear programming (90C05) Integer programming (90C10) Mixed integer programming (90C11) Combinatorial optimization (90C27)
The volume presents the general theory and algorithms essential for nearly all parts of discrete optimization. After a short introduction the material starts in Chapter 2 with complexity theory, more precisely, with time complexity. Here the basic ideas of computability, worst-case analysis and the classes of decision problems P, NP and NP-complete are treated. The subsequent five chapters of the book are dedicated to the algorithmic categories delineated by complexity theory. In Chapters 3 and 4 the authors address time-polynomial procedures. Main topics here are matroids, time-polynomial algorithms in linear programming and their relations to polyhedra arising in combinatorial problems. Chapter 5 deals with partial enumeration procedures. The linear programming based methods are fully considered, along with Lagrangian dual ideas and Benders' decomposition. The alternative to enumeration, i.e. polyhedral description, is focused in Chapter 6. Here, the modern general theory of cutting methods is discussed along with an introduction to the specialized facetial techniques useful for specific problems. Chapter 7 contains nonexact, heuristic procedures. A general discussion of such algorithms is followed by the investigation of greedy, local search, and truncated exponential algorithms. Three appendices dedicated to fundamental results from linear programming, graph theory, convex sets, and polyhedra complete the book. The selection and presentation of the material which covers the main developments in the field of discrete optimization during the past quarter of the century are both nice. Algorithms are written in a computational format and illustrated throughout by examples. The list of references is not comprehensive in the sense of a literature review but reflects the essential papers concerning the given concepts, theorems and algorithms. The book will be very useful for students, instructors and researchers in the field.
- Convergent Lagrangian and domain cut method for nonlinear knapsack problems
- Nonlinear nonconvex optimization by evolutionary algorithms applied to robust control
- Asymptotics of the minimum manipulating coalition size for positional voting rules under impartial culture behaviour
- Optimization of discrete systems
- Integer programs for logic constraint satisfaction
- Paroids: A canonical format for combinatorial optimization
- An intelligent algorithm for mixed-integer programming models
- An adaptation of SH heuristic to the location set covering problem
- Relaxation heuristics for a generalized assignment problem
- Linear programs for constraint satisfaction problems
- Nonlinear integer programming by Darwin and Boltzmann mixed strategy
- The singly constrained assignment problem: A Lagrangian relaxation heuristic algorithm
- An improved branch and bound algorithm for mixed integer nonlinear programs
- Discrete optimization under interval uncertainty
- Global optimization by multilevel search
- A localization and reformulation discrete programming approach for the rectilinear distance location-allocation problem
- A graph approximation heuristic for the vertex cover problem on planar graphs
- Implementation of an integer optimization platform using object oriented programming
- General purpose heuristics for integer programming. I
- A binary integer linear program with multi-criteria and multi-constraint levels
- Disjunctive optimization: Critical point theory
- Lower bound functions for polynomials
- Minimizing the weighted number of tardy jobs on a two-machine flow shop.
- An LP-based algorithm for the data association problem in multitarget tracking.
- \(O(n^ 3)\) noniterative heuristic algorithm for linear programs with error-free implementation.
- Timetable planning using the constraint-based reasoning
- Benders-and-cut algorithm for fixed-charge capacitated network design problem
- Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems
- Strong valid inequalities for fluence map optimization problem under dose-volume restrictions
- Exploiting process plan flexibility in production scheduling: A multi-objective approach
- Lagrangean/surrogate relaxation for generalized assignment problems
- Minimizing the weighted number of tardy jobs on a single machine
- Minimizing the weighted number of tardy jobs on parallel processors
- Smart greedy procedure for solving a nonlinear knapsack class of reliability optimization problems
- Scatter search and star-paths: Beyond the genetic metaphor
- A direct heuristic algorithm for linear programming
- Solving linear programming relaxations associated with Lagrangean relaxations by Fenchel cutting planes
- Valid integer polytope (VIP) penalties for branch-and-bound enumeration
- Discrete optimization in the industrial computer science
- Zero duality gap in surrogate constraint optimization: a concise review of models
- A Lagrangian heuristic for capacitated single item lot sizing problems
- The multiple bottleneck transportation problem
- Parallelizing simulated annealing algorithms based on high-performance computer
- Lagrangean relaxation with clusters for point-feature cartographic label placement problems
- Integer solutions via goal programming to hierarchical systems.
- Decomposition and dynamic cut generation in integer linear programming
- Gomory cuts revisited
- Strong duality in optimization: shifted power reformulation
- Another pedagogy for pure-integer Gomory
- scientific article; zbMATH DE number 4014440 (Why is no real title available?)
- Discrete optimization with bilinear objective function and linear constraints
- OPTi's Algorithm for Discreteness Determination
- New algorithms for pattern matching with wildcards and length constraints
- scientific article; zbMATH DE number 4093169 (Why is no real title available?)
- scientific article; zbMATH DE number 43045 (Why is no real title available?)
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 1157610 (Why is no real title available?)
- Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times
- A hierarchical bicriterion approach to integrated process plan selection and job shop scheduling
- Continuous flow models for batch manufacturing: a basis for a hierarchical approach
- Using Lagrangean relaxation to minimize the weighted number of late jobs on a single machine
- scientific article; zbMATH DE number 752998 (Why is no real title available?)
- Algorithms for solving a separable problem of discrete optimization
- An extension to the single bottleneck transportation problem
- Revival of the Gomory cuts in the 1990's
- Set covering-based surrogate approach for solving sup-\({\mathcal{T}}\) equation constrained optimization problems
- scientific article; zbMATH DE number 5238864 (Why is no real title available?)
- A column generation approach for the maximal covering location problem
- OPTIMAL LOT SOLUTION TO CARDINALITY CONSTRAINED MEAN–VARIANCE FORMULATION FOR PORTFOLIO SELECTION
- An efficient algorithm for nonlinear integer programming problems arising in series–parallel reliability systems
- Online surrogate problem methodology for stochastic discrete resource allocation problem.
- A multi-period network design problem for cellular telecommunication systems
- Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach
- Unlocking Your Bike the Easy Way
- MANPAK: A set of algorithms for computations on implicitly defined manifolds
- An improved branch and bound algorithm for minimum concave cost network flow problems
- On zero duality gap in surrogate constraint optimization: the case of rational-valued functions of constraints
- Discrete optimization: a quantum revolution?
- Generalized surrogate problem methodology for online stochastic discrete optimization
- Polyhedral and Lagrangian approaches for lot sizing with production time windows and setup times
- Scheduling for stability in single-machine production systems
- A facility location model for logistics systems including reverse flows: the case of remanufacturing activities
- Minimizing the weighted number of tardy jobs on a single machine with release dates
- Mathematical programming approach to the Petri nets reachability problem
- A heuristic approach to simultaneous course/student timetabling
- Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem
- Integer programming models for the q-mode problem
- An exact algorithm for cost minimization in series reliability systems with multiple component choices
- Computing exact solution to nonlinear integer programming: convergent Lagrangian and objective level cut method
- A discrete dynamic convexized method for nonlinear integer programming
- Nonlinear discrete optimization. An algorithmic theory
- Optimal harvesting and optimal vaccination
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4040299)