Browse Prior Art Database

Incremental Constraint Deletion for Systems of Linear Constraints

IP.com Disclosure Number: IPCOM000104714D
Original Publication Date: 1993-May-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 118K

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 37% of the total text.

Incremental Constraint Deletion for 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.

Consider a system C of equations,

     a sub 1,1 x sub 1 + a sub 1,2 x sub 2 +  ...  + a sub 1,m x sub
m  =  b sub 1

     a sub 2,1 x sub 1 + a sub 2,2 x sub 2 +  ...  + a sub 2,m x sub
m  =  b sub 2
          .          .               .       .
          .          .               .       .
          .          .               .       .
     a sub n,1 x sub 1 + a sub n,2 x sub 2 +  ...  + a sub n,m x sub
m  =  b sub n
in which some of the x sub i are required to be non-negative.  Any
system of linear equalities and inequalities can be routinely
rewritten into this standard form.  A solved form for C is an
equivalent system of equations, for example S, in which the original
system is "solved" for some of its variables.  It is of the form:
where n prime  le  n and for each x sub i that is required to be
non-negative, b prime sub i is non-negative.  The variables x sub 1,
...,x sub n prime are said to be basic and x sub i is said to be the
basic variable of row i.  The system S can be obtained from C by
repeatedly choosing an equation and "pivoting" on a variable in the
equation so as to eliminate this variable from the other equations.
The problem solved by this invention is, when a constraint is deleted
from C giving a new system of constraints C prime to efficiently
compute a solved form of C prime.  The basic idea behind the
invention is...