Title: Using Matching to Detect Infeasibility of Some Integer Programs,
Abstract: A novel matching based heuristic algorithm designed to detect specially
formulated infeasible zero-one IPs is presented. The algorithm input is a set
of nested doubly stochastic subsystems and a set E of instance defining
variables set at zero level. The algorithm deduces additional variables at zero
level until either a constraint is violated (the IP is infeasible), or no more
variables can be deduced zero (the IP is undecided). All feasible IPs, and all
infeasible IPs not detected infeasible are undecided. We successfully apply the
algorithm to a small set of specially formulated infeasible zero-one IP
instances of the Hamilton cycle decision problem. We show how to model both the
graph and subgraph isomorphism decision problems for input to the algorithm.
Increased levels of nested doubly stochastic subsystems can be implemented
dynamically. The algorithm is designed for parallel processing, and for
inclusion of techniques in addition to matching.