Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Incremental Constraint Deletion of Systems of Linear Constraints

IP.com Disclosure Number: IPCOM000106517D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 116K

Publishing Venue

IBM

Related People

Huynh, T: AUTHOR [+2]

Abstract

Disclosed is a method to incrementally compute the solved form S prime of a subset C prime of the constraints in C with a solved form S Where C is a system of linear equalities and linear inequalities.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

Incremental Constraint Deletion of Systems of Linear Constraints

      Disclosed is a method to incrementally compute the solved form
S prime of a subset C prime of the constraints in C with a solved
form S  Where C is a system of linear equalities and linear
inequalities.

      In applications such as graphical editors, user interface
construction toolkits, and CAD many relationships between objects in
the domain can be naturally expressed a linear equality and
inequality constraints.  For example, the relationship that the
endpoints of two lines touch is represented by an equality between
the co-ordinates of the endpoints of the lines.  In these
applications it is natural to interactively build up systems of such
constraints which allow a high level description of the object, i.e.,
diagram, interface layout, or circuit, being created.  The
constraints are checked for satisfiability and their solution
obtained by computing their solved form.  Because of the incremental
nature of the application, it is important to be able to efficiently
recompute a solved form when constraints are added or deleted.
Previous work on incremental computation of the solved form has
considered the addition of constraints and small changes to the
constraint coefficients, but has not addressed deletion of
constraints.  See [*]  for example.  This invention gives a method
for incrementally recomputing a solved form when a constraint is
deleted from the original system.

      To facilitate the explanation of the invention let C and S be
matrix notation.  C can now be written as Alpha x bar = b bar where
Alpha is an n x m matrix, x bar an m-ary column vector and b bar a
n-ary column vector.  This invention relies on not explicitly
computing S but rather computing an n x n matrix M and n-ary vector v
bar such that (M A)x bar = M b bar corresponds to the solved form S
and v bar sub i is the index of the basic variable in row i of S.
Note that v bar sub i = 0 indicates that row i of S is a row of
"zeroes".  M is called the quasi-inverse matrix and v bar the vector
of basic variables.  Now suppose that the jth constraint is deleted
from C  giving rise to constraint system C prime.  The new constraint
system C prime can be expressed as Alpha prime x bar equals b bar
prime where Alpha prime and b bar prime are obtained by deleting the
jth row from Alpha and b bar respectively.  This invention gives a
method of modifying M and v bar to give an (n-1)x(n-1) matrix M prime
and (n-1)-ary vector v bar prime such that (M prime Alpha prime)x bar
= M prime b prime bar corresponds to a solved form S prime for C
prime with v bar prime sub i the index of the basic variable in row i
of S prime.

      The method to compute M prime and v bar prime from M and v bar
is based on the observation that the jth column in M details how the
jth constraint has been used to obtain the solved form S  The method
works by choosing a pivot row i and then pivoting on p...