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(K₁₂)

Example - 2Lin Facet of P(K₁₂)

Example - 3Lin1Slp Facet of P(K₁₂)

Mappings

Mappings for P(C_n,r): Homomorphisms

Mappings for P(K_n) 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]