F-QLPs over unit relative constraints

Abstract

In this paper, we describe polynomial time algorithms for F-QLPs and F-QIPs over unit relative constraints. Let X = {x1, x2, . . . , xn} denote a set of real-valued variables. Let Y = {y1, y2, . . . , yn} denote a set of range-bound variables with yi ∈ [li, ui], where li, ui ∈ Z. Recall that a relative constraint is a constraint between a pair of variables, i.e., a constraint of the form ai · xi + aj · xj ≤ bij . When both ai and aj belong to the set {−1, 0, 1}, the constraint is said to be a unit relative constraint. A Quantified Linear Program (QLP) is a linear program with a quantifier specification. The quantifier specification includes both existentially quantified variables and universally quantified variables. A QLP can be thought of as a 2-person game, and in this case, the constraint system is called the board of the game. When the universally quantified variables precede the existentially quantified variables in the quantifier specification, the QLP is called an F-QLP. It has been shown that the problem of checking if an F-QLP is feasible is coNP-complete. This paper is concerned with the design of an efficient algorithm for F-QLPs, when the board consists of unit relative constraints. A Quantified Integer Program (QIP) is an integer program with a quantifier specification. F-QIPs are defined as QIPs in which the universally quantified variables precede the existentially quantified variables in the quantifier specification. In this paper, we show that the problem of deciding an F-QIP when the board consists of unit relative constraints is also polynomial time solvable.