TITLE

LP-BASED COMBINATORIAL PROBLEM SOLVING

AUTHOR(S)
Hoffman, K.; Padberg, M.
PUB. DATE
September 1985
SOURCE
Annals of Operations Research;1985, Vol. 4 Issue 1-4, p145
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
A tutorial outline of the polyhedral theory that underlies linear programming (LP)-based combinatorial problem solving is given. Design aspects of a combinatorial problem solver are discussed in general terms. Three computational studies in combinatorial problem solving using the polyhedral theory developed in the past fifteen years are surveyed: one addresses the symmetric traveling salesman problem, another the optimal triangulation of input/output matrices, and the third the optimization of large-scale zero-one linear programming problems.
ACCESSION #
18657743

 

Related Articles

  • A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem. Krishnan, Kartik; Mitchell, John E. // Computational Optimization & Applications;Jan2006, Vol. 33 Issue 1, p51 

    We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this...

  • The Covering Tour Problem. Gendreau, Michel; Laporte, Gilbert; Semet, Frédéric // Operations Research;Jul/Aug97, Vol. 45 Issue 4, p568 

    The Covering Tour Problem (CTP) is defined on a graph G = (V ∪ W, E), where W is a set of vertices that must be covered. The CTP consists of determining a minimum length Hamiltonian cycle on a subset of V such that every vertex of W is within a prespecified distance from the cycle. The...

  • CLUSTERING BASED POLYHEDRAL CONIC FUNCTIONS ALGORITHM IN CLASSIFICATION. OZTURK, GURKAN; CIFTCI, MEHMET TAHIR // Journal of Industrial & Management Optimization;Jul2015, Vol. 11 Issue 3, p921 

    In this study, a new algorithm based on polyhedral conic func tions (PCFs) is developed to solve multi-class supervised data classiffication problems. The k PCFs are constructed for each class in order to separate it from the rest of the data set. The k-means algorithm is applied to find...

  • DCA based algorithms for multiple sequence alignment (MSA). Le Thi, Hoai; Pham Dinh, Tao; Belghiti, Moulay // Central European Journal of Operations Research;Sep2014, Vol. 22 Issue 3, p501 

    In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the...

  • Analysis of the problem of h-polyhedral separability of two sets. Cherneutsanu, E. K. // Vestnik Sankt-Peterburgskogo universiteta, Seriia 7: Geologia, G;2012, Issue 4, p85 

    The problem of strict separation of the convex hull of a finite set A on a finite set B by using h of hyperplanes is considered. This problem is reduced to a finite number of linear programming problems.

  • Analysis of the problem of h-polyhedral separability of two sets. Cherneutsanu, E. K. // Vestnik Sankt-Peterburgskogo universiteta, Seriia 7: Geologia, G;2012, Issue 4, p131 

    The problem of strict separation of the convex hull of a finite set A on a finite set B by using h of hyperplanes is considered. This problem is reduced to a finite number of linear programming problems.

  • Identifying Minimally Infeasible Subsystems of Inequalities. Gleeson, John; Ryan, Jennifer // ORSA Journal on Computing;Winter90, Vol. 2 Issue 1, p61 

    Given an infeasible system of linear inequalities, we show that the problem of identifying all minimally infeasible subsystems can be reduced to the problem of finding all vertices of a related polyhedron. This results in a shorter enumeration than that performed by a previous method to solve...

  • A LEAST-ELEMENT THEORY OF SOLVING LINEAR COMPLEMENTARITY PROBLEMS AS LINEAR PROGRAMS. Cottle, Richard W.; Jong-Shi Pang // Mathematics of Operations Research;May78, Vol. 3 Issue 2, p155 

    In a previous report [2], the authors have established a least-element interpretation to Mangasarian's theory [5], [6] of formulating some linear complementarity problems as linear programs. In the present report, we extend our previous analysis to a more general class of linear complementarity...

  • Absolute Value Equation Solution Via Linear Programming. Mangasarian, Olvi // Journal of Optimization Theory & Applications;Jun2014, Vol. 161 Issue 3, p870 

    By utilizing a dual complementarity property, we propose a new linear programming method for solving the NP-hard absolute value equation (AVE): Ax−| x|= b, where A is an n× n square matrix. The algorithm makes no assumptions on the AVE other than solvability and consists of solving a...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics