Point Containment in the Integer Hull of a Polyhedron1
Ernst Althaus2 Friedrich Eisenbrand2 Stefan Funke2 Kurt Mehlhorn2

2 Related work In two dimensions (d = 2), McCormick, Smallwood and Spieksma [9, 8] developed an algorithm, which runs in time O(m +2 ). Using the equivalence of optimization and separation [5] together with recent algorithms for integer programming [3, 4] one can solve the point containment problem with the ellipsoid method. This 1 Intro duction yields an expected running time of O(m  + 2 log m) 2 We are interested in the point containment problem in for d  3 and a running time of O(m  +  ) for d = 2.  d These algorithms are certifying in our sense. integer hul ls of polyhedra : Given a point x  Q and a McCormick et al. [9, 8] reduce a multiprocessor set of rational constraints Ax  b, A  Qm×d , b  Qm ,  machine scheduling problem to the two-dimensional determine whether x belongs to the convex hull of the integral points satisfying the constraints. Moreover, point-containment problem, where containment has to certify your answer by providing a simplex containing be certified with a unimodular triangle, i.e., with a x which is spanned by feasible integer points in the triangle that does not contain any integer points besides "yes" case, or by providing a halfspace h containing x its vertices. Given any feasible integer triangle T which  such that h  P is integer infeasible in the "no" case. We contains x , one can construct a unimodular triangle Tu d which contains x as follows. use P = {x  R | Ax  b} to denote the polyhedron Compute the integer hulls L and R of the two defined by our set of constraints and PI to denote the polygons T  (x(1)  x (1) ) and T  (x(1)  x (1) ). convex hull of the integral points in P ; PI is frequently The closure of the set T \ (L  R) is a (not necessarily called the integer hul l of P .  Let m be the number of constraints, d the dimension convex) polygon B which contains x . This polygon can of ambient space, and assume that each constraint and be computed in time O() and has O() vertices. Now triangulate B and determine the triangle T containing x has binary encoding length O(). We show: x . This costs again O() [1]. The interior of T does Theorem 1.1. For d = 2, the point containment prob- not contain an integer point and only one edge e of T , lem in integer hul ls of polygons can be solved in time the edge stemming from an edge of B , might contain O(m + ). For d  3 and d fixed, the point containment other integer points. Consider the intersection y  of -  problem in integer hul ls of polyhedra can be solved in the ray - x , where v is the opposite vertex of e, with v, 2 expected time O(m +  log m). this edge e. The two nearest integer points of y  on e, We will make frequent use of the fact that integer together with v form a certifying unimodular triangle. programming can be done in expected time O(m + These two nearest points can be found by solving a  log m) in any fixed dimension [3] and in time O(m + ) one-dimensional integer program, or directly, with one in the two-dimensional case [4]. Also the integer hull of extended gcd-computation. a polygon (vertices in clockwise order) can be computed in time O(m ) in two dimensions [6], in particular the 3 An algorithm for d = 2
1 Partially supp orted by the IST Programme of the EU under contract number IST-1999-14186 (ALCOM-FT) 2 Max-Planck-Institute for Computer Science, Saarbrucken, ¨ Germany

Abstract We show that the point containment problem in the integer hull of a polyhedron, which is defined by m inequalities, with coefficients of at most  bits can be solved in time O(m + ) in the two-dimensional case and in expected time O(m + 2 log m) in any fixed dimension. This improves on the algorithm which is based on the equivalence of separation and optimization in the general case and on a direct algorithm (SODA 97) for the two-dimensional case.

number of vertices of the integer hull is O(m ). We also assume without loss of generality [11] that P is bounded and that PI is full-dimensional.

For a given point x  Q2 , the following simple algorithm solves the point containment problem in the integer hull of a polyhedron P  Q2 in time O(m + ), see Figure 1.

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

929


l v w
PSfrag replacements

and perform one integer hull computation for a constant number of constraints (O()); finding the tangent line can also be done in O() as I has O() vertices. This yields a final running time of O(m + ). Point containment in arbitrary fixed dimension Let us now consider the case d  3. We assume that the integer hull of the polyhedron P is not empty, which can be tested with a call to an optimization oracle. Further we assume without loss of generality that P is bounded and that implicit upper and lower bounds on the variables are part of the constraint set Ax  b. Recall that an inequality aT x   is called valid for P , if all points of P satisfy it. A subset of points F  P , which satisfy a valid inequality aT x   of P with equality is called a face of P . The inequality aT x   is then called the face-defining inequality of F . Given a polytope P , the following procedure computes a simplex  with vertices in PI and x   if and only if x  PI . ContainingSimplex(P , x ) 1. Compute the lexicographically smallest integer point u of PI . - - 2. Determine the last point in PI on the ray u, x and denote it by w. Furthermore, determine a facedefining inequality aT x   of the minimal face of PI containing w. If u = x or if u = w, then return the simplex  = {u}.
c 3. Otherwise, recursively determine the simplex  ontaining w in the integer hull of P = P  (aT x =  ) and return the simplex spanned by u and  .

y I x

4

z

u

Figure 1: The case d = 2. 1. Find an integer point u  P . If x  PI , then x is contained in an integral triangle with vertex u. 2. Determine the constraint aT x   , which defines - - the facet of P which is hit by the ray u, x (ties are broken arbitrarily). 3. Find the optimal integer point v in P w.r.t. to the ob jective function max aT x; let   be the optimal ob jective function value. 4. Let w be the intersection of the line aT x =   - - with u, x . If aT x >   , then x is not contained in PI and we have found a certifying hyperplane, otherwise consider the triangle  = conv(x , v , w) and compute its integer hull I . Note that  is contained in P . 5. Compute the line l which intersects x and is tangential to I such that u and I lie on the same side of l. Let y be the first vertex of I which lies on l, starting from x . 6. Perform an integer feasibility test for P intersected with the halfspace h defined by the closure of the side of l which does not contain I . Any integer point z in the resulting polygon must be opposite of y on the line through u and x . Thus conv(u, y , z ) is a certifying triangle. If no integer point exists in this polygon, then x is not contained in PI . A certifying hyperplane can then be determined by slightly rotating the line l around y . This rotation can be determined by similar means with which we determined y in Step 5. For the running time, observe that we have to solve a constant number of optimization problems (O(m + ))

The so constructed simplex is unique and denoted by (x , P ). Before we begin with an analysis of this approach, let us define the height  (x , P ) of x and P , which is a tuple. If the simplex (x , P ) consists of u alone, then  (x , P ) = (u). Otherwise, let h be the distance from u to w. The height is then recursively defined as the tuple  (x , P ) = (u, -h,  (w, P  (aT x =  )). In the following, we assume that the height  (x , P ) is a 2 d+1tuple by appending -components to right of the tuple defined above. Given x , we define an order P x Q if  (x , P ) lex  (x , Q) for polytopes P, Q  Rd . Notice that  (x , P ) =  (x , Q) if and only if the simplices (x , P ) and (x , Q) are equal. Furthermore we have the following lemma. Lemma 4.1. Let P  Rd and Q  Rd be polytopes and x  Rd . If P  Q, then  (x , Q) lex  (x , P ) and

930


thus Q x P . Moreover,  (x , Q) <lex  (x , P ) iff a The dual of this linear program has the following vertex of (x , Q) is not contained in P . form: Proof. Let P = (x , P ) and Q = (x , Q). Let uP and uQ , denote the lexicographically smallest integer point of P and Q respectively. Since uP  Q we have uQ lex uP . If they differ, we have  (x , Q) <lex  (x , P ) and a vertex of Q is not contained in P . We now assume that uP = uQ and denote this point by u. If u = x , Q = P = {u} and  (x , P ) = (u, , . . . , ) =  (x , Q). So assume u = x and let wP and wQ be the last vertices in the - - boundary of PI and QI , respectively, on the ray u, x and let FP and FQ be the minimal faces containing these points, respectively. Since PI  QI , wQ does not pre- - cede wP on u, x . If wQ = u, Q = P = {u} and   (x , P ) = (u, , . . . , ) =  (x , Q). So assume wQ = u. If wP = wQ , wQ  PI and  (x , Q) <lex  (x , P ). Also, wQ  FQ and hence is contained in the simplex Q , where Q is the simplex determined in step 3 of ContainingSimplex(Q, x ). Since wQ  PI , one of the vertices of Q is not contained in PI . We now assume wP = wQ and wQ = u and use w to denote wQ . Let aT x  Q be a face-defining inequality Q FQ . Remember that  (x , Q) = (u, -h,  (w, FQ )) and that  (x , P ) = (u, -h,  (w, FP )). The assertion then follows by induction if one can show that FP  FQ holds. Since PI  QI the inequality aT x  Q is faceQ defining for PI . The face FP of PI , defined by this inequality contains w and thus FP , by the minimality of FP . The integer points in FP lie in PI and hence in QI and they satisfy aT x  Q with equality. Thus Q FP  F P  F Q .
4.1 Details of Step 2 We now analyze the running time of the above procedure. We assume that P is represented by a system Ax  b, where A  Qm×n and b  Qm . Again,  denotes the largest binary encoding length of a coefficient of A, b and x . Step 1 of the above procedure takes an expected number of O(m +  log m) steps, whereas step 2 can be solved in expected time O(m + 2 log m) as follows: Let (xi )iI be the set of vertices of PI . The intersection point w of the ray starting at u through x with the boundary of PI is the last point of the ray that is a convex combination of points in (xi )iI . Thus the following linear program finds the intersection point w. max s.t.  i u + (xi - u) = I i xi i = 1 I 0 min s.t. yT u + z y T (x - u) -y T xi + z

=1 0

It has d + 1 variables. The separation problem for the dual is an optimization over the integer hull of ¯ P (For an alleged solution (y T , z ) compute maxi y T xi ¯¯ and check the inequality. The d equalities can be checked easily). Thus the separation problem can be solved in time O(m +  log m) and hence the linear program can be solved via the ellipsoid method [5] in time O(m  + 2 log m). It remains to show, how to compute the facedefining inequality aT x   of the minimal face of PI containing w. This is done as follows, see also [5, p. 183, theorem 6.5.8]. We look for a valid inequality that is tight at w with smallest possible dimension, i.e. the number of affinely independent points of PI that are tight at w should be as small as possible. Let Q be the polytope Q = {(z T , µ)T  Rd+1 | z T x  µ for all x  PI , z T w = µ}, which is the polytope of valid inequalities for PI which are tight at w. A point in the relative interior of this set defines a face of minimal dimension that is tight at w. The separation problem for this polytope is again an optimization problem over the integer hull of P . Thus the optimization problem over Q can be solved in time O(m  + 2 log m). Within this time-bound one can find a point (aT ,  )T in the relative interior of Q. The inequality aT x   is the face-defining inequality we are looking for. Therefore the overall running time of this procedure on a polytope defined by m constraints in d dimensions is O(m + 2 log m) for fixed d. So the running time is dominated by Step 2. 4.2 The size of a basis In the following we apply the machinery of LP-type problems such that this step has to be performed O(log m) times on subproblems of constant size. A smallest (number of constraints) subsystem A x  b of Ax  b with (x , Ax  b) = (x , A x  b ) is called a basis of Ax  b. The goal of this section is to show, that the number of constraints of a basis of Ax  b is bounded by a constant. The following theorem is due to Scarf [10], see also [11, p. 234]. Theorem 4.1. Let Ax  b be a system of inequalities in d variables, and let c  Rd . If max{cT x | Ax  o b, x  Zd } is finite, then there exists a subset A x  b f Ax  b with at most 2d - 1 inequalities, such that the

931


to fix the lexicographically minimal vertex u of PI and to detect the case, where w = u. Thus if k = 1 the max{cT x | Ax  b, x  Zd } assertion holds. Suppose now that k  2. Again, by Corollary 4.1, = max{cT x | A x  b , x  Zd } there exists a subset A x  b defining a polyhedron Q, -  From this one can immediately infer the next state- such that the ray - x leaves QI also in the point w u, T ment, which is useful in our setting. and such that a x   defines the minimal face of PI containing w if and only if aT x   defines the minimal Corollary 4.1. Let P = {x  Rd | Ax  b} be a face of QI containing w. rational polyhedron and let FP  PI be a face of PI . This means that there exists a subset of 4 d (2d - 1) Then there exists a subsystem A x  b of Ax  b, which constraints with respect to which the first two steps consists of at most 2 d (2d - 1) constraints, defining a of the procedure ContainingSimplex yields the same polyhedron Q = {x  Rd | A x  b }, such that there result. The assertion then follows by induction. exists a face FQ of QI with FP  FQ and dim(FP ) = dim(FQ ). Furthermore, an inequality aT x   is a face4.3 The LP-typ e problem We now model the defining inequality of FP if and only if aT x   is a search for a constant size subset A x  b of Ax  b, face-defining inequality of FQ . such that (x , Ax  b) = (x , A x  b ) as an LPtype problem. Such an LP-type problem [7] is specified Proof. The polyhedron PI can be described as by a pair (H,  ), where H is a finite set, whose elements PI = {x  Rd | A= x = b= }  {x  Rd | A+ x  b+ }, are called constraints and  : 2H  W is a function with values in a linearly ordered set (W , ) satisfying such that the following conditions hold, see [11, p. 103]: a certain set of axioms (see below). The goal is to The matrix A= has full row-rank and d1 rows, where compute a minimal subset BH of H with the same value d - d1 is the dimension of PI . Furthermore each as H . In our setting the set H consists of the constraints constraint of A+ x  b+ is irredundant and each row defining P . For a subset F  H , we denote by P (F ) of A+ is orthogonal to the rows of A= . the polytope which is defined by F and the implicit A face FP of PI of dimension k  d - d1 is upper and lower bounds. We then define  (F )   (G) determined by d-d1 -k linearly independent constraints if P (F ) x P (H ). The following axioms are satisfied. Ax  b from the set A+ x  b+ which are satisfied Axiom 1.(Monotonicity) For any F, G with F  G  by FP with equality. It follows from Theorem 4.1 that H , we have  (F )   (G). there exists a subset A x  b of Ax  b with at most This axiom is immediate by Lemma 4.1, since 2 d (2d - 1) constraints, defining a polyhedron Q, such P (G)  P (F ). that A= x = b= and Ax  b are valid for QI , where Axiom 2.(Locality) For any F  G  H with  (F ) = Q = {x  Rd | A x  b }. The face FQ of QI which  (G) and any h  H ,  (G) <  (G  {h}) implies that results from setting the constraints in Ax  b to equality also  (F ) <  (F  {h}). contains FP and has dimension k . If  (F ) =  (G) holds, then the simplices Furthermore, an inequality aT x   is a face- (x , P (F )) and (x , P (G)) coincide. If  (G) < defining inequality of FP or of FQ if and only if a =  (G  {h}), then h cuts off a vertex of this simplex µ A= +  A and  = µ b +  b, where µ  Rd1 ,   (Lemma 4.1). Consequently also  (F ) strictly increases. A basis BG of a subset G  H is a minimal subset of Rd-d1 -k and  is strictly positive. G with  (BG ) =  (G). The combinatorial dimension This enables us to estimate the size of a basis of of a LP-type problem is the size of the largest basis Ax  b. of any G  H . From Lemma 4.2, we know that the combinatorial dimension of our problem is constant. Lemma 4.2. Let P = {x  Rd | Ax  b} be a An LP-type problem of constant combinatorial dipolytope in fixed dimension d with nonempty integer mension can be solved with O(m) violation tests and hul l. Suppose that (x , Ax  b) has k vertices. Then O(log m) basis computations for constant size subsets there exists a subset A x  b of the constraints Ax  b, of constraints, as shown in [2, 7]. A violation test for a with at most (2k - 1) 2 d (2d - 1) constraints, such that basis B and a constraint h is the problem of determining the simplices (x , Ax  b) and (x , A x  b ) are whether  (B ) =  (B  {h}). A basis computation for equal. a set of constraints G is the task of computing a basis Proof. We use induction on the number k . It follows of G. Let us first deal with the violation test. Let B from Corollary 4.1 that 2 d (2d - 1) constraints suffice

following equality holds

932


be a basis. A constraint violates this basis, if and only if it cuts off (at least) one of the corner points of (x , P (B )). Thus, we iterate over the corners of the simplex and check violation. This requires constant time. For the basis computation, let G  H be a subset of the constraints of constant size. We have to compute the simplex (x , P (F )) for each F  G and choose the smallest set F with (x , P (F )) = (x , P (G)). This can be done by calling our procedure ContainingSimplex(G, x ) a constant number of times. These calls cost O(2 ). This shows that one can compute (x , Ax  b) and a basis A x  b of Ax  b in expected time O(m + 2 log m). Recall that x  PI if and only if x  (x , Ax  b) if and only if x is in the integer hull of A x  b . If x is not in (x , Ax  b) we can compute a separating hyperplane of x from the integer hull of A x  b in O(2 ) steps, using the equivalence of separation and optimization. All-together we have shown that the point containment problem in the integer hull of a polyhedron can be solved in an expected number of O(m + 2 log m) operations. This concludes the proof of Theorem 1.1. References
[1] B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6(5):485­524, 1991. [2] K. L. Clarkson. Las vegas algorithms for linear and integer programming when the dimension is small. Journal of the Association for Computing Machinery, 42:488­499, 1995. [3] F. Eisenbrand. Fast integer programming in fixed dimension. In G. D. Battista and U. Zwick, editors, In Proceedings of the 11th Annual European Symposium on Algorithms, ESA' 2003, volume 2832 of LNCS, pages 196­207. Springer, 2003. [4] F. Eisenbrand and S. Laue. A faster algorithm for two variable integer programming. In 14th Annual International Symposium on Algorithms and Computation, ISAAC 03, LNCS. Springer, 2003. to appear. [5] M. Grotschel, L. Lovasz, and A. Schrijver. Geometric ¨ ´ Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer, 1988. [6] W. Harvey. Computing two-dimensional integer hulls. SIAM Journal on Computing, 28(6):2285­2299, 1999. [7] J. Matouek, M. Sharir, and E. Welzl. A subexpos nential bound for linear programming. Algorithmica, 16(4-5):498­516, 1996. [8] S. T. McCormick, S. R. Smallwood, and F. C. R. Spieksma. Polynomial algorithms for multiprocessor scheduling with a small number of job lengths. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), pages 509­517, New York, 1997. ACM.

[9] S. T. McCormick, S. R. Smallwood, and F. C. R. Spieksma. A polynomial algorithm for multiprocessor scheduling with two job lengths. Mathematics of Operations Research, 26(1):31­49, 2001. [10] H. E. Scarf. An observation on the structure of production sets with indivisibilities. Proc. Nat. Acad. Sci. U.S.A., 74(9):3637­3641, 1977. [11] A. Schrijver. Theory of Linear and Integer Programming. John Wiley, 1986.

933