Publication:3818127
From MaRDI portal
zbMath0665.90063MaRDI QIDQ3818127
Publication date: 1986
Lagrangian relaxation; polyhedra; branch and bound; integer linear programming; cutting planes; blocking; linear inequalities; total dual integrality; Benders' decomposition; ellipsoid method; antiblocking; totally unimodular matrices
90C10: Integer programming
90C05: Linear programming
90-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
Related Items
Convexity and global optimization: A theoretical link, Complexity of the gravitational method for linear programming, Some results on universal minimal total dominating functions, Convexity recognition of the union of polyhedra, Perfect, ideal and balanced matrices, A method of transferring polyhedron between the intersection-form and the sum-form, On the relationship between the integer and continuous solutions of convex programs, Optimal piecewise linear schedules for LSGP- and LPGS-decomposed array processors via quadratic programming, Automatic implementation of affine iterative algorithms: Design flow and communication synthesis, Automatic derivation of probabilistic inference rules, On the optimum of Delsarte's linear program, An algorithmic approach to Schmüdgen's Positivstellensatz, On the complexity of recognizing the Hilbert basis of a linear Diophantine system, Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning, Reachable and controllable sets for two-dimensional, linear, discrete- time systems, Some efficient solutions to the affine scheduling problem. II: Multidimensional time, Optimal loop storage allocation for argument-fetching dataflow machines, Synthesis aspects in the design of efficient processor arrays from affine recurrence equations, Geometrical tools to map systems of affine recurrence equations on regular arrays, Optimal distributed execution of join queries, A singular loop transformation framework based on non-singular matrices, Algorithmic characterizations of interval orderd hypergraphs and applications, The expressive power of voting polynomials, Random walks, totally unimodular matrices, and a randomised dual simplex algorithm, Polyhedral consequences of the amalgam operation, Near-perfect matrices, New contraction methods for linear inequalities, A nonsmooth variant of the Mangasarian-Fromovitz constraint qualification, On skew primeness of inner functions, Incorporating processor costs in optimizing the distributed execution of join queries, Computing over the reals with addition and order, On the complexity of quadratic programming in real number models of computation, Geometric comparison of combinatorial polytopes, Characterizing consistency in probabilistic logic for a class of Horn clauses, On the \(k\)-cut subgraph polytope, Enclosing solutions of linear interval equations is NP-hard, Asymptotic analysis of the exponential penalty trajectory in linear programming, The design of optimum component test plans in the demonstration of system reliability, Inferences in probability logic, Three, four, five, six, or the complexity of scheduling with communication delays, Some applications of nonnegative linear systems: Farkas strikes again, A branch bound method for subset sum problem, Realizations with a cut-through Eulerian circuit, Fuzzy refutations for probability and multivalued logics, On the complexity of some basic problems in computational convexity. I. Containment problems, Lattice-free polytopes and their diameter, Multivariate discrete distributions induced by an urn scheme, linear Diophantine equations, unbiased estimating, testing and applications, Resolution and the integrality of satisfiability problems, Asymptotic convergence in a generalized predictor-corrector method, Subsumtion and indexing in constraint query languages with linear arithmetic constraints., Computational complexity and constraint logic programming languages, Standard forms for rational linear arithmetic in constraint logic programming., Fractional v. integral covers in hypergraphs of bounded edge size, Utility function programs and optimization over the efficient set in multiple-objective decision making, The volume of relaxed Boolean-quadric and cut polytopes, Extremal problems for finite sets and convex hulls---a survey, Optimal constant weight codes over \(Z_k\) and generalized designs, Minimizing the response time of executing a join between fragmented relations in a distributed database system, Binary vectors partially determined by linear equation systems, Linear programming, the simplex algorithm and simple polytopes, Discrete optimization in public rail transport, Simplices by point-sliding and the Yamnitsky-Levin algorithm, The complexity and approximability of finding maximum feasible subsystems of linear relations, Utility efficiency and its approximation, Probabilistic biclassification and random variable representations, Real data-integer solution problems within the Blum-Shub-Smale computational model, The complexity of query evaluation in indefinite temporal constraint databases, Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case, The parsimonious property of cut covering problems and its applications, Complexity of searching an immobile hider in a graph, On essential components and critical sets of a graph, Dual reduction and elementary games, The height of minimal Hilbert bases, Majorization, polyhedra, and statistical testing problems, Minimal systems of generators for ideals of semigroups, Consistency, redundancy, and implied equalities in linear systems, Finding the minimum weight IIS cover of an infeasible system of linear inequalities, On the two-connected planar spanning subgraph polytope, The design of a 0-1 integer optimizer and its application in the Carmen system, From local to global consistency in temporal constraint networks, Queries with arithmetical constraints, Avoiding slack variables in the solving of linear diophantine equations and inequations, Auditing Boolean attributes, The doubly graded matrix cone and Ferrers matrices, Canonical modules of certain edge subrings, Complete description of a class of knapsack polytopes., Improved bound for the Carathéodory rank of the bases of a matroid, Packing cycles in graphs, Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets, A greedy algorithm for convex geometries, On the normality of Rees algebras associated to totally unimodular matrices, A compact linear program for testing optimality of perfect matchings., Relative volumes and minors in monomial subrings., Integer programming, Barvinok's counting algorithm and Gomory relaxations., Rational and integral \(k\)-regular matrices., System theory for system identification., Two sensitivity theorems in fuzzy integer programming., On the computational complexity of upper total domination, Edge-disjoint odd cycles in planar graphs., Counting the solutions of Presburger equations without enumerating them., Cutting planes from a mixed integer Farkas lemma., On the qualitative approximation of Lipschitzian functions., An algorithm for approximate multiparametric linear programming, A short proof of a theorem of Falmagne., On the directed hop-constrained shortest path problem, Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions, Decomposition of balanced matrices, Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights, Linear-shaped partition problems, Mathematical problems for the next century, On the properties of the subsets of a discrete domain defined by the local optimae of a function endowed with some geometrical properties, A polyhedral approach to sequence alignment problems, Minimal-volume shadows of cubes, Interval analysis: Theory and applications, Planning and acting in partially observable stochastic domains, Supernormal vector configurations, From monomials to words to graphs., A linear programming algorithm for invariant polyhedral sets of discrete-time linear systems, A theory of even functionals and their algorithmic applications, Combination techniques and decision problems for disunification, Integral self-affine tiles in \(\mathbb{R}^n\). II: Lattice tilings, A weak version of the Blum, Shub, and Smale model, Perfect \(0,\pm 1\) matrices, Interval propagation to reason about sets: Definition and implementation of a practical language, Computability of recurrence equations, Bounded discrete representations of interval orders, On the finite convergence of interior-point algorithms for linear programming, Some efficient solutions to the affine scheduling problem. I: One- dimensional time, A path-following procedure to find a proper equilibrium of finite games, The anti-join composition and polyhedra, On Fourier's algorithm for linear arithmetic constraints, On cuts and matchings in planar graphs, Convergence behavior of interior-point algorithms, A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio, Concave extensions for nonlinear 0-1 maximization problems, Geometry, complexity, and combinatorics of permutation polytopes, Ear decomposition for pair comparison data, Hamiltonian tournaments and Gorenstein rings, Non-standard approaches to integer programming, Ideal clutters, Cutting planes in integer and mixed integer programming, Integral rigid sets and periods of nonexpansive maps, Foundations of aggregation constraints, Affine scheduling on bounded convex polyhedric domains is asymptotically optimal, A dual projective simplex method for linear programming, Multi-criteria analysis with partial information about the weighting coefficients, Elementary divisors of graphs and matroids, A class of invariant regulators for the discrete-time linear constrained regulation problem, Global convergence of the affine scaling methods for degenerate linear programming problems, An interior point algorithm to solve computationally difficult set covering problems, The symbiotic relationship of combinatorics and matrix theory, Traveling salesman games, Induced binary probabilities and the linear ordering polytope: A status report, Expressing combinatorial optimization problems by linear programs, A canonical form for generalized linear constraints, The distance to a polyhedron, Optimal partitions having disjoint convex and conic hulls, A geometric view of parametric linear programming, On integer points in polyhedra, Generalized transitive tournaments and doubly stochastic matrices, Lattice translates of a polytope and the Frobenius problem, Coflow polyhedra, Generalization of Karmarkar's algorithm to convex homogeneous functions, On interior algorithms for linear programming with no regularity assumptions, A note on approximate linear programming, Matching theory -- a sampler: From Dénes König to the present, Circuits in graphs embedded on the torus, A characterization of the uncapacitated network design polytope, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, A decomposition theory for matroids. VII: Analysis of minimal violation matrices, Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem, Probabilistic logic programming, Lattice matrices, intersection of ring families and dicuts, On polynomial solvability of the high multiplicity total weighted tardiness problem, Note on lattice-point-free convex bodies, A computational basis for higher-dimensional computational geometry and applications, A combined constraint-space, objective-space approach for determining high-dimensional maximal efficient faces of multiple objective linear programs, LP relaxation of the two dimensional knapsack problem with box and GUB constraints, Polytopes related to the \(l_{\infty}\)-distance between vectors, Stability aspects of the traveling salesman problem based on \(k\)-best solutions, Adjacency on the constrained assignment problem, More tight monomials in quantized enveloping algebras, The optimal path-matching problem, On the stochastic independence properties of hard-core distributions, The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable, On packing connectors, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, A note on formulations for the \(A\)-partition problem on hypergraphs, On the invariance of solutions of finite games, A cutting-plane approach to mixed 0-1 stochastic integer programs, The complexity of multidimensional periodic scheduling, On the complexity of smooth projective toric varieties, Algorithms for matrix groups and the Tits alternative, Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming, Weak \(k\)-majorization and polyhedra, Balinski-Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces, Discrete convex analysis, Standard pairs and group relaxations in integer programming, Using SAGBI bases to compute invariants, Test sets of integer programs, Torus quotients of homogeneous spaces, Maximal unimodular systems of vectors, Representations and characterizations of vertices of bounded-shape partition polytopes, A primal dual integer programming algorithm, A model for the assignment of candidates to constituencies in a mixed election system, A semantical framework for supporting subjective and conditional probabilities in deductive databases, Degeneracy in interior point methods for linear programming: A survey, Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems, On lengths of non-unique factorizations and systems of linear diophantine inequalities, A linear constraint satisfaction approach to cost-based abduction, Directed Steiner problems with connectivity constraints, Finding an interior point in the optimal face of linear programs, Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming, Implied constraints and a unified theory of duality in linear and nonlinear programming, Querying temporal and spatial constraint networks in PTIME, Optimising the flow of information within a C3I network., Linear measurement models -- axiomatizations and axiomatizability, Obtaining simultaneous solutions of linear subsystems of inequalities and duals, Short vectors of planar lattices via continued fractions, An intersection theorem on an unbounded set and its application to the fair allocation problem, Totally tight Chvatal-Gomory cuts, A phase-1 approach for the generalized simplex algorithm, Length-bounded disjoint paths in planar graphs, On point-duration networks for temporal reasoning, Discrete convexity and unimodularity. I., Duality gaps in nonconvex stochastic optimization, A linear algorithm for integer programming in the plane, On exact selection of minimally unsatisfiable subformulae, Optimization with additional variables and constraints, Reachable, controllable sets and stabilizing control of constrained linear systems, Checking robust nonsingularity is NP-hard, Gainfree Leontief substitution flow problems, Three algorithms for bicriteria integer linear programs, Evaluating multiple join queries in a distributed database system, An identity for matching and skew-symmetric determinant, On the minors of an incidence matrix and Smith normal form, The core of games on convex geometries, Algebraic algorithms for sampling from conditional distributions, Constraint-generating dependencies, Solving interval linear systems with linear programming techniques, Generalized optimal lattice covering of finite-dimensional Euclidean space, The size of triangulations supporting a given link, A lower bound for the job insertion problem., A logic for reasoning about probabilities, Cutting-plane proofs in polynomial space, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, Combinatorial optimization and small polytopes, A proof of the branching number bound for normal manifolds, Consistency problems in ER-schemas for database systems, \(\mathbb N\)-solutions to linear systems over \(\mathbb Z\), Investigations on autark assignments, Dynamic multi-objective heating optimization, Analytic centers and repelling inequalities, Graph imperfection. I, Polynomials associated with nowhere-zero flows, Optimal ear decompositions of matching covered graphs and bases for the matching lattice, On the submodular matrix representation of a digraph., Representation-finite triangular algebras form an open scheme, Logarithm-free \(A\)-hypergeometric series, On greedy bases packing in matroids, The vertex ideal of a lattice., Linear control of live marked graphs, Solving the knapsack problem via \(\mathbb Z\)-transform, Minimal-volume projections of cubes and totally unimodular matrices, The max-plus algebra of the natural numbers has no finite equational basis, On the solution sets of particular classes of linear interval systems, Learning from rounded-off data., Equational theories of tropical semirings, An algebra-based approach for linearly constrained concave minimization, Dynamic of error diffusion on several polytopes, Local base station assignment with time intervals in mobile computing environments, Finite generation of rings of differential operators of semigroup algebras., A vector partition function for the multiplicities of \(\mathfrak{sl}_k\mathbb C\), Some characterizations of minimal Markov basis for sampling from discrete conditional distribu\-tions, The synthesis of Petri nets from path-automatic specifications, A polynomiality property for Littlewood-Richardson coefficients, A note on tolerance graph recognition, Minimizing maximum indegree, On the even permutation polytope, Efficient solution generation for multiple objective linear programming based on extreme ray generation method, Application of cut polyhedra. I, Applications of cut polyhedra. II, Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs, Bounding the piercing number, An identity for bipartite matching and symmetric determinant, Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form, An algorithm for large scale 0-1 integer programming with application to airline crew scheduling, Refined proximity and sensitivity results in linearly constrained convex separable integer programming, Complete linear descriptions of small asymmetric traveling salesman polytopes, Executing join queries in an uncertain distributed environment, Separation and approximation of polyhedral objects, Undecidability of restricted uniform recurrence equations, Allocating relations in a distributed database system, Totally unimodular Leontief directed hypergraphs, On the classification of geometric codes by polynomial functions, A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts, Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems, Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems, An algebraic geometry algorithm for scheduling in presence of setups and correlated demands, On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope, Beyond unimodular transformations, On strictly proper equilibria, Metric subgraphs of the chamfer metrics and the Melter-Tomescu path generated metrics, Stability critical graphs and ranks facets of the stable set polytope, The propagation of updates to relational tables in a distributed database system, Mapping 3-D IIR digital filter onto systolic arrays, A closed-form representation of mixed-integer program value functions, Strong connectivity of polyhedral complexes, On the partial order polytope of a digraph, Reverse search for enumeration, On preemptive scheduling: A general setting for the two-phase method, Time-tables, polyhedra and the greedy algorithm, Cardinality-restricted chains and antichains in partially ordered sets, The dominant of the 2-connected-Steiner-subgraph polytope for \(W_ 4\)-free graphs, Modelling cyclicity and generalized cost-based abduction using linear constraint satisfaction, Convergence in Karmarkar's algorithm: a review, Some more n‐dimensional geometry†, Lattice Points of Cut Cones, A Variant of the Dual Pivoting Rule in Linear Programming, Continuous selections of linear functions and nonsmooth critical point theory, Consumption and Portfolio Policies With Incomplete Markets and Short‐Sale Constraints: the Finite‐Dimensional Case1, Two‐stage stochastic integer programming: a survey, (Deterministic) algorithms that compute the volume of polytopes, COMPILE TIME PARTITIONING OF NESTED LOOP ITERATION SPACES WITH NON-UNIFORM DEPENDENCES*, Affine semigroup rings that are complete intersections, An approach to production planning and scheduling in cyclically scheduled manufacturing systems, Recognizing Units in Number Fields, Graphs with the Circuit Cover Property, Short rational generating functions for lattice point problems, On the equations defining toric l.c.i.-singularities, A LIBRARY FOR DOING POLYHEDRAL OPERATIONS, Unnamed Item, Space-Time Equations for Non-Unimodular Mappings, Uniform bounds on multigraded regularity, Polyhedral techniques in combinatorial optimization I: Theory, A Modified Termination Rule for Karmarkar’s Algorithm, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, The theory of linear programming:skew symmetric self-dual problems and the central path*, Small Cones of Oriented Semi-Metrics, On the Monotone Upper Bound Problem, A PARALLEL ALGORITHM FOR FIXED-DIMENSIONAL LINEAR PROGRAMMING∗, The interior-point revolution in optimization: History, recent developments, and lasting consequences, Qualitative aspects of the local approximation of a piecewise differentiable function, Discrete subadditive functions as Gomory functions, STEADY-STATE SCHEDULING ON HETEROGENEOUS CLUSTERS, ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING, On the Use of Duality and Pricing Criteria in the Generalized‐simplex Method, A survey of computational complexity results in systems and control, Finite and infinite dimensional generalizations of Klyachko's theorem, Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks, On rigidity and realizability of weighted graphs, On the core of transportation games, A generalized Sylvester identity and fraction-free random Gaussian elimination, Computing an integer point of a simplex with an arbitrary starting homotopy-like simplicial algorithm, An algorithm for finding the first excited state in the random-field Ising model, An algorithm for finding MAPs for belief networks through cost-based abduction, Local optimality subsets and global optimization: A prospective approach, Fair division of indivisible items among people with similar preferences, On the Petri net realization of context-free graphs, On computing Hilbert bases via the Elliot--MacMahon algorithm, Cutting corners, Random generation of finite Sturmian words, Constructing the value function for an integer linear programme over a cone, Packing Steiner trees: Polyhedral investigations, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, Balanced \(0,\pm 1\)-matrices, bicoloring and total dual integrality, Applying Lehman's theorems to packing problems, Mixed-volume computation by dynamic lifting applied to polynomial system solving, Tessellation and \(g\)-tessellation of circulants, \(Q_ 6\), and \(Q_ 6^ t\), Periodic network optimization with different arc frequencies, Ideal polytopes and face structures of some combinatorial optimization problems, A proof of the optimality of the MIN paging algorithm using linear programming duality, On the Chvátal rank of polytopes in the 0/1 cube, Optimising the distributed execution of join queries in polynomial time, Fiber polytopes for the projections between cyclic polytopes, \((A,B)\)-invariant polyhedral sets of linear discrete-time systems, An integer programming problem and rank decomposition of block upper triangular matrices, Note on a paper of Broyden, Decompositions of edge-colored complete graphs, The column-circular, subsets-selection problem: Complexity and solutions, On lattice points in polyhedral cross-sections, Generating functions and duality for integer programs, A discrete Farkas lemma, The selection and scheduling of telecommunication calls with time windows, The complexity of finite model reasoning in description logics, A branch-and-cut algorithm for scheduling of projects with variable-intensity activities, The design of optimum component test plans in the demonstration of a series system reliability, General models in min-max planar location: Checking optimality conditions, Low-complexity algorithms for sequencing jobs with a fixed number of job-classes, The complementary-slackness class of hybrid systems, Subtractive reductions and complete problems for counting complexity classes, Matrices defining Gorenstein lattice ideals, Totally expanding multiplicative systems, Polytopes of partitions of numbers, A symbolic decision procedure for cryptographic protocols with time stamps, A computational study of integer programming algorithms based on Barvinok's rational functions, The average shadow price for MILPs with integral resource availability and its relationship to the marginal unit shadow price, Dynamic decision making without expected utility: an operational approach, A note on the Rees algebra of a bipartite graph, An asymptotically exact algorithm for the high-multiplicity bin packing problem, Distance matrix and Laplacian of a tree with attached graphs, Rees algebras of square-free Veronese ideals and their a-invariants, Multiplicities of edge subrings, Normality of semigroups with some links to graph theory., Permutohedra and minimal matrices, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Representation theory, dynamical systems, combinatorial and algorithmic methods. Part 10. Transl. from the Russian., The number of Reidemeister moves needed for unknotting, Convex polytopes all of whose reverse lexicographic initial ideals are squarefree, FIRST SYZYGIES OF TORIC VARIETIES AND DIOPHANTINE EQUATIONS IN CONGRUENCE, Agrégation des similarités : une solution oubliée, Weyl-minkowski duality for integarl monoids*, A simplex-like method with bisection for linear programming1, Piercing convex sets
