Can I read Optimal Length Cutting Plane Refutations of Integer Programs on EtoBox?

Optimal Length Cutting Plane Refutations of Integer Programs by K. Subramani; P. Wojciechowski is a book available to read on EtoBox.

What is Optimal Length Cutting Plane Refutations of Integer Programs about?

In this paper, we discuss the computational complexities of determining optimal length refutations of infeasible integer programs (IPs). We focus on three different types of refutations, namely readonce refutations, tree-like refutations, and dag-like refutations. For each refutation type, we are interested in finding the length of the shortest possible refutation of that type. For our purposes, the length of a refutation is equal to the number of inferences in that refutation. The refutations in this paper are also defined by the types of inferences that can be used to derive new constraints. We are interested in refutations with two inference rules. The first rule corresponds to the summation of two constraints and is called the ADD rule. The second rule is the DIV rule which divides a constraint by a positive integer. For integer programs, we study the complexity of approximating the length of the shortest refutation of each type (read-once, tree-like, and dag-like). In this paper, we show that the problem of finding the shortest read-once refutation is NPO PB-complete. Additionally, we show that the problem of finding the shortest tree-like refutation is NPO-hard for IPs. We al

Author

K. Subramani; P. Wojciechowski

Publisher

Springer International Publishing : Imprint: Springer

Published

2023

Language

EN

ISBN

9783031252112

Subjects

Computer Science, Stem