A Cutting Plane Algorithm for the Linear Ordering Problem
From MaRDI portal
Publication:3217947
DOI10.1287/opre.32.6.1195zbMath0554.90077OpenAlexW2099103397MaRDI QIDQ3217947
Michael Jünger, Martin Grötschel, Gerhard Reinelt
Publication date: 1984
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.32.6.1195
heuristicspolyhedral combinatoricslinear ordering problemNP-hard combinatorial optimizationbranch and bound techniquescutting plane procedureone-machine schedulingaggregation of individual preferencestriangulation of input-output tables
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Multisectoral models in economics (91B66) Individual preferences (91B08) Polytopes and polyhedra (52Bxx)
Related Items
On the acyclic subgraph polytope, Facets of the linear ordering polytope, Two-edge connected spanning subgraphs and polyhedra, Solving matching problems with linear programming, The linear ordering problem with clusters: a new partial ranking, A note on small linear-ordering polytopes, A branch-and-cut algorithm for vehicle routing problems, The Boolean Quadric Polytope, Applying mod-\(k\)-cuts for solving linear ordering problems, The linear ordering problem revisited, Nonnormal deterministic equivalents and a transformation in stochastic mathematical programming, Disentangling relationships in symptom networks using matrix permutation methods, The reversing number of a digraph, Computing minimal forecast horizons: an integer programming approach, Quadratic assignment problems on series-parallel digraphs, A survey on the linear ordering problem for weighted or unweighted tournaments, Tabu search for the dynamic bipartite drawing problem, An inexact algorithm for the sequential ordering problem, Dynamic bundle methods, A polynomial-time solution to Papadimitriou and Steiglitz's ``traps, Semidefinite relaxations of ordering problems, Robust Learning of Consumer Preferences, Fairness and the set of optimal rankings for the linear ordering problem, Solving real-world linear ordering problems using a primal-dual interior point cutting plane method, Voting schemes for which it can be difficult to tell who won the election, On discrete optimization with ordering, Strong formulations for mixed integer programming: A survey, Facets of the balanced (acyclic) induced subgraph polytope, A cutting plane algorithm for a clustering problem, Maximum planar subgraphs and nice embeddings: Practical layout tools, An integer programming approach for the search of discretization orders in distance geometry problems, Experiments in quadratic 0-1 programming, Facets and lifting procedures for the set covering polytope, An exact algorithm for the edge coloring by total labeling problem, Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date, A minimum violations ranking method, Developing a ranking problem library (RPLIB) from a data-oriented perspective, An Exact Method for the Minimum Feedback Arc Set Problem, Could we use a million cores to solve an integer program?, Revised GRASP with path-relinking for the linear ordering problem, A linear ordering problem with weighted rank, Optimal solutions for the double row layout problem, A branch-and-bound algorithm for the linear ordering problem with cumulative costs, A benchmark library and a comparison of heuristic methods for the linear ordering problem, A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments, The generalized assignment problem: Valid inequalities and facets, Randomized Algorithms for Lexicographic Inference, A production planning problem in FMS, On approximability of linear ordering and related NP-optimization problems on graphs., Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis, A branch-and-cut algorithm for a resource-constrained scheduling problem, Tabu search tutorial. A graph drawing application, Classical cuts for mixed-integer programming and branch-and-cut, Ising formulations of some graph-theoretic problems in psychological research: models and methods, An integer programming approach to optimal basic block instruction scheduling for single-issue processors, A cutting plane algorithm for the windy postman problem, A tutorial on branch and cut algorithms for the maximum stable set problem, The linear ordering problem with cumulative costs, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Analysis of a generalized linear ordering problem via integer programming, Multiprocessor scheduling under precedence constraints: polyhedral results, On the Hardness of Approximating Some NP-optimization Problems Related to Minimum Linear Ordering Problem, The linear ordering problem: instances, search space analysis and algorithms, Variable neighborhood search for the linear ordering problem, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, A branch and bound algorithm for the minimum storage-time sequencing problem, Block-insertion-based algorithms for the linear ordering problem, New exact approaches to row layout problems, Valid inequalities and facets of the capacitated plant location problem, Cutting-plane proofs in polynomial space, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, Combinatorial optimization and small polytopes, A new heuristic algorithm solving the linear ordering problem, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Facets and algorithms for capacitated lot sizing, On the linear ordering problem and the rankability of data, Computing in combinatorial optimization, Models for concurrent product and process design, Workload balancing and loop layout in the design of a flexible manufacturing system, A semidefinite optimization approach for the single-row layout problem with unequal dimensions, A polyhedral approach to sequence alignment problems, On the optimal modeling and evaluation of job shops with a total weighted tardiness objective: constraint programming vs. mixed integer programming, Unnamed Item, A cutting-plane approach to the edge-weighted maximal clique problem, A technique for speeding up the solution of the Lagrangean dual, The Rankability of Data, A combinatorial study of partial order polytopes
Uses Software
