From: lepape@ilog.fr (Claude Le Pape)
Newsgroups: comp.ai
Subject: Re: regions within regions
Date: 2 Sep 92 12:24:17 GMT
Reply-To: lepape@ilog.UUCP (Claude Le Pape)
Organization: ILOG SA, 2, Avenue Gallieni, BP 85, F-94253 Gentilly Cedex, FRANCE


In article <1992Aug28.211428.148200@Cookie.secapl.com> frank@Cookie.secapl.com
(Frank Adams) writes:

> In article <SJAMESON.92Aug13083908@fergie.atl.ge.com> sjameson@atl.ge.com
(Stephen M Jameson) writes: 

>> In article <3753@keele.keele.ac.uk> csa09@seq1.keele.ac.uk (Paul Singleton)
>> writes:

>>> I have some regions in N-space, each defined by a simple set 
>>> of constraints,
>>> e.g.
>>> 	0 =< X =< 5         (1)
>>> 	0 =< Y =< 5         (2)
>>> 	2 =< Z =< 7         (3)
>>>	0 =< X+Y =< 8       (4)
>>> 
>>> and I need an algorithm (for general N) to determine whether one region
>>> completely encloses another.

>>
>> This is based on about 5 minutes of pen-pushing, so it may need some
>> smoothing of the rough edges, but your algorithm will be based on
>> the following three facts:
>>
>> ...

> Since nobody else has done so, let me note that this is *not* a solution, or
> even much of a start at a solution. This is a "linear programming" problem;
> accept no substitutes.

Even though I ---in this particular case--- agree with the
conclusion, I am afraid the sententious sentence above (This is a
"linear programming" problem; accept no substitutes) does not provide
very valuable information to Paul Singleton. Of course his problem IS
a LINEAR problem, but there are many particular types of linear
problems for which a general linear programming algorithm is not the
most appropriate (e.g., critical path problems).

The problem that P. Singleton wants to solve seemingly has an important
characteristic: all the coefficients of variables are equal to 1. This
may suggest that an efficient algorithm ---more efficient than general
linear programming--- exists or may exist for such a problem. In fact
it happens that every linear problem with integral (or rational)
coefficients/constants can be rewritten as a linear problem with
coefficients of variables equal to 1.

Proof: Just iterate with the three following rules.

	      * If (- x) appears in an equation, define a new variable
		x' and add the equation   0 <= x + x' <= 0.
		Then replace (- x) everywhere by x'.

	      * If (* n x) with n even in Z-{0} appears in an equation,
		define three new variables x' x'' x''' and add the 
		equations:
			0 <= x  + x' + x'' <= 0
			0 <= x  + x''' <= 0
			0 <= x' + x''' <= 0
		and replace (* n x) everywhere by (* -n/2 x'').

	      * If (* n x) with n odd in Z-{-1 1} appears in an equation,
		define three new variables x' x'' x''' and add the
		equations:
			0 <= x  + x' + x'' <= 0
			0 <= x  + x''' <= 0
			0 <= x' + x''' <= 0
		and replace (* n x) everywhere by (+ (* (1-n)/2 x'') x)
		
Note that this transformation does LINEARLY increase the size of the
problem (assumming log(n) bits are necessary to represent n). Hence
the worst-case complexity of P. Singleton's problem is at least that
of general linear programming with integral (or rational)
coefficients/constants. This ---and only this--- suggests that the use
of a general linear programming algorithm is a reasonable option
---from a purely algorithmic point of view (with no software
integration or possible software evolution concerns) and assuming the
problems to solve do not have another, more exploitable, common
characteristic.

Claude Le Pape

-- 
  Claude LE PAPE		 net : lepape@ilog.fr
  ILOG S.A.
  2 Avenue Gallieni - BP 85	 tel : (33 1) 46 63 66 66
  94253 Gentilly Cedex FRANCE	 fax : (33 1) 46 63 15 82
Newsgroups: comp.ai