Accession Number:

ADA289397

Title:

Using the Dimension Reduction Technique to Prove that Clique Trees Define Facets for the Asymmetric Traveling Salesman Polytope.

Descriptive Note:

Research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

• Carr, Bob

Report Date:

1994-09-14

Pagination or Media Count:

59.0

Abstract:

In this paper the author develops a new general approach to proving that a given inequality is facet-defining. This approach is then used to show that clique tree inequalities define facets for the asymmetric traveling salesman problem.

Descriptors:

• *PROBLEM SOLVING
• SIZES(DIMENSIONS)
• GRAPHS
• REDUCTION
• ASYMMETRY
• COMBINATORIAL ANALYSIS
• FAULT TREE ANALYSIS
• CONVEX SETS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE