Systems of Simultaneous Inequalities

By Mark Austin,2014-06-20 19:01
16 views 0
Systems of Simultaneous Inequalities

Fourth LACCEI International Latin American and Caribbean Conference on Engineering and Technology (LACCEI ‘2006)

    Breaking Frontiers and Barriers in Engineering: Education, Research and Practice”, 21-23 June 2006, Mayaguez, Puerto Rico

    Systems of Inequations

    Jeffrey L. Duffany, Ph.D.

    Universidad del Turabo

    Gurabo, PR USA


    A system of inequations is equivalent to the compatibility problem which is one of the best known and classic examples of np-complete problem. A solution method is described which is analogous to solving systems of equations using substitution and elimination of variables. A decision function is used to determine which variables to combine. The solution method can be implemented using set-theoretical operators such as union and intersection or using a combination of modular and traditional arithmetic operators. The performance of the basic method is shown to be significantly improved when used in a variation called the equivalence class subset algorithm.

    1 Introduction

    A system of inequations is represented by a set of n variables and a set of compatibilities involving all xi

    pairs of variables. For example suppose n=2 and the system is represented by inequation (1): (x,x)ij

     (1) x(x12

For this example and is a solution as is and , since both satisfy every x1x2xpxnp1212

    inequation in the system. In general, the solution to a system of inequations is drawn from an arbitrary set of distinct elements. There are an infinite number of solutions to this system but a solution s* is called optimal only if the number of elements in the solution set is minimum over all possible solution sets {s}. In this case the cardinality of the optimal solution k*=max(s*) is 2 since s*={1,2} is a solution and it is not possible to solve this system with a set of lower cardinality. The cardinality of a solution k=max(s) is

    not the same as the cardinality of the solution |s| which is always equal to the dimension of the system

    (i.e., the number of variables “n”). A system of inequations can be represented by a binary symmetric square matrix A, with a zero representing a compatibility and a one an incompatibility as in equation (2).

    01?) (2) A??10(

The matrix A in equation (2) is a representation of the system of inequations. There are always x(x12

    two ones in the A matrix for every inequation representing both and . A system of x(xx(xijji

    inequations can also be represented by inequation (3):

     (3) Ax(x

if the addition operator “+” in the vector product is replaced by the union () set operator. The variable

     is represented as the first row of column vector x and is represented by the second row of column xx12

    vector x. Analogous to a matrix representation of equations, inequation (3) represents a system of inequations of the form . Note that “”in inequation (3) is interpreted differently from (x(xx...ijk

    standard usage when either side of the expression is a set of variables. In this case the “” symbol (

    distributes over each element of the set. In other words, is equivalent to inequations x(xxijk

    and. Another way to express this would be using the set-theoretical (not a member of) x(xx(x~ijik

    symbol. However the symbol will be used to emphasize the similarity between systems of equations (

    and systems of inequations. Systems of inequations are equivalent to the well-known compatibility problem[Clay,2005] which is categorized as NP-hard[Weisstein, 2005a][Horowitz, 1978]. 2 Substitution and Elimination of Variables

    A solution technique for systems of inequations can be defined which is analogous to the technique used for systems of equations, also known as the method of substitution and elimination of variables. This method always finds a feasible solution “s” but the solution that it finds may or may not be optimal. An example of substitution of variables is given by the following pair of inequations (4) where variable is x1

    used to substitute for and eliminate variable: x4

x(xx123 (4) x(xxx?1235x(xx435

Since there is no constraint that in the pair of inequations (4) it is possible to set x = xx and x(x11414

    eliminate x (the symbol “” representing the union operator). The union operator can be considered the 4

    set-theoretical equivalent of the addition operator. The combined inequations assert that x ? x and that 12

    x ? x and that x ? x. An optimal solution is given by s*=(1,2,2,1,2). The substitution of x for x 131514

    results in x=x=1 and x=x=x=2 in the optimal solution. The variables have been partitioned into two 14235

    sets {x,x} and {x,x,x}. Since k*=2 any optimal solution will partition the variables into two sets each 14235

    of which is referred to as an equivalence class or independent set. This leads to the following observation.

Observation: For any system of inequations any two variables that are in the same equivalence class of

    any optimal solution can be associated to create a new system of inequations which has the same optimal solution cardinality k* as the original system.

    Combining variables in this fashion will always lead to a feasible but not necessarily optimal solution. This process can be continued until eventually for all pairs of variables . At this point x(x(x,x)ijij

    either an optimal solution s* has been found or a feasible but not optimal solution s(k>k*) has been found. Back substitution is used to find the solution for the original system.

    For every system of n inequations there is at least one optimal solution of minimum cardinality k* and exactly one trivial solution s(n)={1,2,3…n}. The trivial solution s(n) represents the association of each

    variable to a different integer, i{1,2,3,..n}. In the system the unique optimal solution s* xix(xi12

    and the trivial solution s(n) are the same s*=s(n)=(1,2). It should also be noted that in this case the number of solutions of cardinality less than k*=2 and greater than n=2 is zero. In general, any solution that is not optimal has cardinality k>k* and can be referred to as a suboptimal solution. For any given system there can be a large number of suboptimal solutions for k*

    The number of pairs of variables that can be substituted for one another in a given system is an integer between 0 and n(n-1)/2 inclusive. Finding an optimal solution for a system of inequations is equivalent to having a decision function that can for any A matrix select two variables that are in the same equivalence class of some optimal solution s* in {s*}. For any system of inequations the set X of off-diagonal zeros of the matrix A represent the set of all pairs of variables that can be combined into equivalence classes X={xi,xj | a=0, ij}. If |X|=0 (X={}) then the system is called a complete system. For any system that (ij

    is not complete there is always at least one pair of variables that when combined leads to an optimal solution. If |X|=n(n-1)/2 then all variables are in the same equivalence class and X=X, where X is the ecec

    subset of X corresponding to an optimal or suboptimal solution “s” X={xi,xj|xi,xj in s}. ec

    Finding an optimal solution for a system of inequations can be accomplished by finding a mapping function f(X) which partitions the set X= {xi,xj | aij=0} into two mutually exclusive subsets XX=X, ac

    X?X={}. The set X represents the subset of X for which the variables xi and xj can be found in the acc

    same equivalence class of at least one optimal solution. The set X represents the subset of X for which a

    the variables (xi,xj) are never found in the same equivalence class of any optimal solution. The subscripts c and a of X and X are abbreviations of the words chromatic and achromatic. If two variables are ac

    combined and the cardinality of an optimal solution of the new A’ matrix is the same as the original A

    matrix then the operation it can be said to represent a chromatic transformation. If not then it can be said

    to be an achromatic transformation. Without loss of generality the mapping function f(X) can be referred