Constraint-optimization method for document layout using tradeoff generation

• US 20070006072A1
• Filed: 06/29/2005
• Published: 01/04/2007
• Est. Priority Date: 06/29/2005
• Status: Abandoned Application

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Purvis, Lisa
• Application Number:
  US11/170,610
• Publication Number:
  US 20070006072A1
• Time in Patent Office: Days
• US Class Current: 715/249
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191

Abstract

A method for automated document layout using interactive tradeoff generation during the optimization of a constraint satisfaction problem (CSP) is provided. The method includes generating a constraint satisfaction problem describing the layout of the items in the document as a problem having constraints, finding inconsistent constraints which are incapable of being satisfied together, generating tradeoffs for the inconsistent constraints capable of eliminating one or more of the inconsistent constraints, choosing one or more of the tradeoffs as being one or more acceptable tradeoffs and using them to optimize the CSP to arrive at an optimized document layout.

Claims

1. a method of determining a document layout of items in a:

document comprising;

a. generating a constraint satisfaction problem describing the layout of the items in the document as a problem having constraints;

b. determining if the constraints are optimized;

c. finding inconsistent constraints which are incapable of being satisfied together;

d. generating tradeoffs for the inconsistent constraints capable of eliminating one or more of the inconsistent constraints;

e. a user choosing one or more of the tradeoffs as being one or more acceptable tradeoffs thereby forming revised constraints;

f. replacing constraints with revised constraints; and

g. repeating steps b-f until all constraints are optimized to no longer produce inconsistent constraints thereby determining a layout for the document.

2. The method defined in claim 1 wherein the step of finding inconsistent constraints comprises finding one set of inconsistent constraints which are incapable of being satisfied together.

3. The method defined in claim 1 wherein the step of finding inconsistent constraints comprises finding a plurality of sets of inconsistent constraints, wherein the inconsistent constraints in a set are incapable of being satisfied together.

4. The method defined in claim 3 wherein the step of generating tradeoffs further comprises generating a number of solutions to the optimization algorithm which identify tradeoffs to eliminate at least one of the plurality of sets of inconsistent constraints.

5. The method defined in claim 1 wherein the step of finding inconsistent constraints comprises using a consistency checking technique.

6. The method defined in claim 5 wherein the consistency checking technique comprises arc-consistency.

7. The method defined in claim 1 wherein the step of generating tradeoffs for the inconsistent constraints occurs during the optimization of the constraint satisfaction problem.

8. The method defined in claim 1 wherein the step of a user choosing one or more of the tradeoffs as being one or more acceptable tradeoffs occurs during the optimization of the constraint satisfaction problem.

9. A method of determining a document layout of items in a document comprising:

a. generating a constraint satisfaction problem describing the layout of the items in the document as a problem having constraints;

b. determining if the constraints are optimized;

c. finding inconsistent constraints which are incapable of being satisfied together;

d. generating tradeoffs during the optimization of the constraint satisfaction problem for the inconsistent constraints, the tradeoffs being capable of eliminating one or more of the inconsistent constraints;

e. a user choosing one or more of the tradeoffs as being one or more acceptable tradeoffs during the optimization of the constraint satisfaction problem thereby forming revised constraints;

f. replacing constraints with revised constraints; and

g. repeating steps b-f until all constraints are optimized to no longer produce inconsistent constraints thereby determining a layout for the document.

10. The method defined in claim 9 wherein the step of finding inconsistent constraints comprises finding one set of inconsistent constraints which are incapable of being satisfied together.

11. The method defined in claim 9 wherein the step of finding inconsistent constraints comprises finding a plurality of sets of inconsistent constraints, wherein the inconsistent constraints in a set are incapable of being satisfied together.

12. The method defined in claim 11 wherein the step of generating tradeoffs further comprises generating a number of solutions to the optimization algorithm which identify tradeoffs to eliminate at least one of the plurality of sets of inconsistent constraints.

13. The method defined in claim 9 wherein the step of finding inconsistent constraints comprises using a consistency checking technique.

14. The method defined in claim 13 wherein the consistency checking technique comprises arc-consistency.