Cyclic Group and Knapsack Facets

Motivation

Topics

Problem Definitions

Subadditive Characterizations

Knapsack facets

Some Covering Facets

Relationship between Problems

3 Approaches to Facet Generation

Seeds

Example - (1,0,-1) Facet of P(K12)

Example - 2Lin Facet of P(K12)

Example - 3Lin1Slp Facet of P(K12)

Mappings

Mappings for P(Cn,r): Homomorphisms

Mappings for P(Kn) from cyclic groups (i)

Tilting Knapsack Facets

Tilting Knapsack Facets-Example

Tilting Knapsack Facets

Tilting Knapsack Facets-Extension

Tilting Knapsack Facets-Extension

Generating Facets-Summary

Gomory’s Shooting Experiment

Shooting Theorem

Additive Relations vs Hits-C(23,22)

Additive Relations vs Hits-C(24,23)

Shooting Results for Facet Classes

Generating and Shooting Results

Generating Cutting Planes

Subadditive Functions     f:[0,1] ® [0,1]