EXTRACTION OF LOGICAL RELATIONS AND DUALITY GAP

This paper studies the determination of the permanent of a system of 0-1 linear constraints, i.e. the set of variables with a fixed value in every feasible solution. First, it is recalled how one can extract logical relations by using surrogate constraints in a system of 0-1 linear constraints. In the case of variables with a fixed value (unary relations), it is shown that the efficiency of the method depedns on the value of the duality gap of an optimization probme deduced from the system 0-1 linear constraints. The results obtained are illustrated on a voting confidentiality problem which can be formulated either as an extension of a generalized assignment problem or as a partitioning problem. It is shown that, depending on the formulation, the number of variables of the permanent one can identify changes and that the differences can be explained in terms of duality gap. (A)

• Corporate Authors:

  CENTRE DE RECHERCHE SUR LES TRANSPORTS. UNIVERSITE DE MONTREAL

  C.P. 6128, SUCCURSALE A
  MONTREAL, QUEBEC  Canada  H3C 3J7
• Authors:
  • JAMARD, B
  • Soumis, F
• Publication Date: 1988

Language

• English

Media Info

• Features: References;
• Pagination: 22 p.
• Serial:
  • CENTRE DE RECHERCHE SUR LES TRANSPORTS PUBLICATION
  • Issue Number: 458-A
  • Publisher: Universite de Montreal

Subject/Index Terms

• TRT Terms: Calculation; Economic efficiency; Mathematical models; Optimization
• Uncontrolled Terms: Efficiency; Optimum
• ITRD Terms: 6464: Calculation; 5911: Efficiency; 6473: Mathematical model
• Subject Areas: Economics;

Filing Info

• Accession Number: 00674509
• Record Type: Publication
• Source Agency: Transportation Association of Canada (TAC)
• Files: ITRD
• Created Date: Mar 8 1995 12:00AM