Paroids: A canonical format for combinatorial optimization

Almost all successful exact approaches to hard combinatorial optimization problems are firmly rooted in the theory of a single canonical model formate-linear integer programming. Some heuristic or approximate strategies for hard combinatorial problems are also structures around linear programming, but many of the most effective, including greedy and local search schemes have no close ties to the linear format. This paper introduces a new structure the authors call a paroid which they believe has the potential to remedy these difficulties by providing a purely combinatorial canonical format in which discrete problems can be ‘naturally’ modeled, and in which notions of combinatorial search can be studied and compared. A paroid is formed by a matroid and a partition of the underlying ground set into ‘all or nothing’ parity sets. The authors offer as exemplars fairly natural paroid optimization formulations for seven classical combinatorial problems. Then a structural hierarchy of paroids is introduced and many of the seven models are seen to fall in the easiest class. The authors show that standard matroid theory can be extended with natural notions of paroid duals and minors, and investigate invariances over the present classes. Finally, they briefly review earlier results showing the power of a generic paroid search algorithm to unitfy a number of quite diverse combinatorial algorithms.