Incremental Linear Constraint Solving and Detection of Implicit Equalities

The incremental linear constraint satisfaction problem consists of repeatedly solving the satisfiability problem for a growing set of linear constraints. This problem is important to constraint logic programming systems where constraints are discovered one at a time and added to a current constraint set, and the satisfiability of this constraint set must be known at all times. Implicit equalities of a system of constraints are inequality constraints that are satisfied as an equality in all solutions of the system of constraints. Detecting implicit equalities is important in determining the minimal (canonical) representation of a system of linear constraints. In incremental constraint solving systems detecting implicit equalities provides information that can simplify further constraint solving. We present an algorithm which efficiently solves the incremental linear constraint satisfaction problem and detects all the implicit equalities present in the constraints. The algorithm forms a basis for the inequa...

• Publication year

  1991

• Venue

  INFORMS journal on computing

• Publication date

  1991-11-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1287/ijoc.3.4.269
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• No references are available for this paper.

• Finding a maximal element of a non-negative convex set through its characteristic cone: an application to finding a strictly complementary solution

  2018cites this paper
• Multicore SMT scheduling of periodic task systems with energy minimization

  2016cites this paper
• Finding a maximal element of a non-negative convex set through its characteristic cone: an application to finding a strictly complementary solution

  2016cites this paper
• Typing linear constraints

  2010cites this paper
• Equality detection for linear arithmetic constraints

  2009cites this paper
• 4. Further Applications

  2007cites this paper
• Constraint Logic Programming

  2006cites this paper
• Handbook of Constraint Programming

  2006cites this paper
• Simplify: a theorem prover for program checking

  2005cites this paper
• Consistency, redundancy, and implied equalities in linear systems

  2005cites this paper
• Solving Numerical Constraints

  2001cites this paper
• Icola — Incremental Constraint-Based Graphics for Visualization

  1998cites this paper
• Early Projection in CLP(R)

  1998cites this paper
• Approaches to the Incremental Detection of Implicit Equalities with the Revised Simplex Method

  1998cites this paper
• A bibliography for the development of an Intelligent Mathematical Programming System

  1996cites this paper
• Backtracking without trailing in CLP (ℜLin)

  1995cites this paper
• Backtracking without trailing in CLP (RLin)

  1994cites this paper
• Constraint Logic Programming: A Survey

  1994cites this paper
• The use of the optimal partition in a linear programming solution for postoptimal analysis

  1994cites this paper
• Contraint Logic Programming - An Informal Introduction

  1992cites this paper
• The CLP(R) Programmer's Manual Version 1.2

  1992cites this paper
• Standard forms for rational linear arithmetic in constraint logic programming

  1992cites this paper
• The CLP( ℛ ) language and system

  1992cites this paper
• Constraint logic programming

  1991cites this paper