Abstract
Cutting plane methods require the solution of a sequence of linear programs, where the solution to one provides a warm start to the next. A cutting plane algorithm for solving the linear ordering problem is described. This algorithm uses the primaldual interior point method to solve the linear programming relaxations. A point which is a good warm start for a simplex-based cutting plane algorithm is generally not a good starting point for an interior point method. Techniques used to improve the warm start include attempting to identify cutting planes early and storing an old feasible point, which is used to help recenter when cutting planes are added. Computational results are described for some real-world problems; the algorithm appears to be competitive with a simplex-based cutting plane algorithm.
Similar content being viewed by others
References
M. Grötschel and O. Holland, Solution of large-scale travelling salesman problems, Mathematical Programming 51 (1991) 141.
M.W. Padberg and G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33 (1991) 60.
I.J. Lustig, R.E. Marsten and D.F. Shanno, On implementing Mehrotra's predictor-corrector interior point method for linear programming, SIAM Journal on Optimization 2 (1992) 435.
M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for the linear ordering problem, Operations Research 32 (1984) 1195.
M. Jünger,Polyhedral Combinatorics and the Acyclic Subdigraph Problem (Heldermann, Berlin, 1985).
G. Reinelt,The Linear Ordering Problem: Algorithms and Applications (Heldermann, Berlin, 1985).
J.E. Mitchell and B. Borchers, A primal-dual interior point cutting plane method for the linear ordering problem, COAL Bulletin 21 (1992) 13.
S. Chopra, E.R. Gorres and M.R. Rao, Solving the Steiner tree problem on a graph using branch and cut, ORSA Journal on Computing 4 (1992) 320.
M. Grötschel and O. Holland, Solving matching problems with linear programming, Mathematical Programming 33 (1985) 243.
M. Grötschel, C.L. Monma and M. Stoer, Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints, Operations Research 40 (1992) 309.
B. Borchers and J.E. Mitchell, Using an interior point method in a branch and bound algorithm for integer programming, Technical Report 195, Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY, 12180 (1991).
IBM, IBM Optimization Subroutine Library Guide and Reference, Publication number SC23-0519-1, New York (1990).
R.E. Bixby and M.J. Saltzman, Recovering an optimal LP basis from an interior point solution, Operations Research Letters 15 (1994) 169.
N. Megiddo, On finding primal- and dual-optimal bases, ORSA Journal on Computing 3 (1991) 63.
R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten and D.F. Shanno, Very large-scale linear programming: A case study in combining interior point and simplex methods, Operations Research 40 (1992) 885.
J.L. Goffin and J.P. Vial, Cutting planes and column generation techniques with the projective algorithm, Journal of Optimization Theory and Applications 65 (1990) 409.
J.L. Goffin, A. Haurie and J.P. Vial, Decomposition and nondifferentiable optimization with the projective algorithm, Management Science 38 (1992) 284.
J.E. Mitchell and M.J. Todd, Solving combinatorial optimization problems using Karmarkar's algorithm, Mathematical Programming 56 (1992) 245.
J.A. Kaliski and Y. Ye, A decomposition variant of the potential reduction algorithm for linear programming, Management Science 39 (1993) 757.
G.B. Dantzig and Y. Ye, A build-up interior method for linear programming: Affine scaling form, Technical Report SOL 90-4, Systems Optimization Laboratory, Dept. of Operations Research, Stanford University, Stanford, CA 94305, USA (1990).
M.G.C. Resende and G. Veiga, An efficient implementation of a network interior point method, in:Network Flows and Matching: First DIMACS Implementation Challenge, ed. D.S. Johnson and C.C. McGeogh, DIMACS Series on Discrete Mathematics and Theoretical Computer Science (1993).
R.V. Helgason and J.L. Kennington, NETFLO, Computer Program, Operations Research Department, Southern Methodist University, Dallas, TX (1985).
D. den Hertog, C. Roos, and T. Terlaky, A build-up variant of the path-following method for LP, Operations Research Letters 12 (1992) 181.
D.S. Atkinson and P.M. Vaidya, A cutting plane algorithm for convex programming that uses analytic centers, Mathematical Programming 69 (1995) 1.
I.J. Lustig, R.E. Marsten and D.F. Shanno, Starting and restarting the primal-dual interior point method, Technical Report SOR 90-14, School of Engineering and Applied Science, Dept. of Civil Engineering and Operations Research, Princeton University, Princeton, NJ 08544, USA (1990).
N.K. Karmarkar, M.G.C. Resende and K.G. Ramakrishnan, An interior point algorithm to solve computationally difficult set covering problems, Mathematical Programming 52 (1991) 597.
R.M. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations, ed. R.E. Miller and J.W. Thatcher (Plenum Press, 1972).
I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Linear Algebra and its Applications 152 (1991) 191.
Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM Journal on Optimization 4 (1994) 208.
A.S. El-Bakry, R.A. Tapia and Y. Zhang, A study of indicators for identifying zero varables in interior-point methods, SIAM Review 36 (1994) 45.
M. Grötschel, M. Jünger and G. Reinelt, Optimal triangulation of large real-world input-output matrices, Statistische Hefte 25 (1984) 261.
J.J. Dongarra, Performance of various computers using standard linear equations software, Technical Report CS-89-85, Computer Science Department, University of Tennessee, Knoxville, TN 37996-1301 (1995).
CPLEX Optimization Inc., Using the CPLEX Callable Library, Suite 279, 930 Tahoe Blvd., Bldg 802, Incline Village, NV 89541 (1994).
I.J. Lustig, R.E. Marsten and D.F. Shanno, Interior point methods for linear programming: Computational state of the art, ORSA Journal on Computing 6 (1994) 1.
C. Roos and J.P. Vial, A polynomial method of approximate centers for linear programming, Mathematical Programming 54 (1992) 295.
K.M. Anstreicher, A combined phase I- phase II scaled potential algorithm for linear programming, Mathematical Programming 52 (1991) 429.
S. Mizuno, M. Kojima and M.J. Todd, Infeasible-interior-point primal-dual potential-reduction algorithms for linear programming, SIAM Journal on Optimization 5 (1995) 52.
J.E. Mitchell, An interior point column generation method for linear programming using shifted barriers, SIAM Journal on Optimization 4 (1994) 423.
D. den Hertog, Interior point approach to linear, quadratic and convex programming, algorithms and complexity, Ph.D. thesis, Faculty of Mathematics and Informatics, TU Delft, NL-2628 BL Delft, The Netherlands (1992).
Author information
Authors and Affiliations
Additional information
Research partially supported by ONR Grant number N00014-90-J-1714.
Rights and permissions
About this article
Cite this article
Mitchell, J.E., Borchers, B. Solving real-world linear ordering problems using a primal-dual interior point cutting plane method. Ann Oper Res 62, 253–276 (1996). https://doi.org/10.1007/BF02206819
Issue Date:
DOI: https://doi.org/10.1007/BF02206819