as a PDF
Contents
1. Cassowary in Smalltalk and QOCA in C They perform surprisingly well and a summary of our results is given in Section 5 The QOCA implementation is considerably more sophisticated and has much better performance than the current version of Cassowary However QOCA is inherently a more complex algorithm and re implementing it with a comparable level of performance would be a daunting task In contrast Cas sowary is straightforward and a reimplementation based on this paper is more reasonable given a knowledge of the sim plex algorithm A companion technical report 6 gives addi tional details for both algorithms 1 4 Related Work There is a long history of using constraints in user interfaces and interactive systems beginning with Ivan Sutherland s pi oneering Sketchpad system 20 Most of the current sys tems use one way constraints e g 13 17 or local prop agation algorithms for acyclic collections of multi way con straints e g 19 21 Indigo 2 handles acyclic collections of inequality constraints but not cycles simultaneous equa tions and inequalities UI systems that handle simultaneous linear equations include DETAIL 12 and Ultraviolet 3 A number of researchers including the first author have exper imented with a straightforward use of a simplex package in a UI constraint solver but the speed was not satisfactory for interactive use An earlier version of QOCA is described in references 10 and2. are active Thus AY 1 3 4 is the initial active set The equality constrained optimization problem of is therefore minimize f subject to 22m RE Aap 0 x 100 T 0 The problem oP has only one feasible solution m 50 x 0 2 100 so it is also the optimal solution de noted by xj Next we check if x9 is the optimal solution to the problem P Constraint 4 forces x to take the value 0 in x5 However the value of the objective function f can be reduced if x is increased Thus the 4th constraint x gt 0 can be moved out of the active set in order to further reduce the value of f This gives x x as the new approximate so lution AW 1 3 as the active set and the optimization problem ol as minimize f subject to 22m z Ir 0 Zp 100 To solve o we rewrite the constraints in o to a basic feasible solved form x 100 A a 2 100 and then eliminate basic variables in the function f This results in the following unconstrained optimization problem minimize 2 50 2am 100 30 100 70 Setting the derivative to be zero we obtain 2 am 50 2 x 2 2 m 130 0 Solving this together with the constraint in of the optimal solution of of is found to be xt 62 24 100 T It is easy to verify that xj is still feasible Similarly to the case for Xg 1n xj r is forced to take the value 100 because of the 3rd constraint yet the function
3. re ferred to as QP minimize f subject to C where f g wi ai di The variables are x1 n and C is the set of required constraints The desired value for variable x is d and the weight associated with that desire which should reflect the hierarchy is w This problem is a type of quadratic programming in which a quadratic optimization function is minimized with respect to a set of linear arithmetic equality and inequality constraints In particular since the optimization function is a sum of squares the problem is an example of convex quadratic pro gramming meaning that the local minimum is also the global minimum This is fortunate since convex quadratic program ming has been well studied and efficient methods for solv ing these problems are well known in the operations research community 4 1 Active Set Method Our implementation of QOCA uses the active set method 8 to solve the convex quadratic programming problem This method is an iterative technique for solving constrained op timization problems with inequality constraints It is reason ably robust and quite fast and is the method of choice for medium scale problems consisting of up to 1000 variables and constraints The key idea behind the algorithm is to solve a sequence of constrained optimization problems Oo O Each problem minimizes f with respect to a set of equality constraints A called the active set The active set consis
4. 1 by 1000 am 60 reflecting the change in the objective func tion A solved form for these equations is 500 5 te Tm 20 2 which leads to the optimal solution for both oP and QP as m 59 98 x 39 98 r 79 98 The exact least squares better solution is actually x 60 z 40 2 80 With quadratic optimization the strong constraints don t completely dominate the weak ones in the computed solution However by choosing a suitably large constant we found a solution that is least squares better to under a one pixel res olution so that the deviation from a least squares better so lution would not be visible in an interactive system See 6 for more on this issue To modify the active set method so that it is incremental for resolving we observe that changing the desired variable val ues only changes the optimization function f Thus we can reuse the active set from the last resolve and reoptimize with respect to this In most cases the active set does not change and so we are done Otherwise we proceed as above For example if we now move m from 60 to 90 we change the objective function again but need only change the de sired values and can keep the weights the same as they are in fo e g in the new objective function f3 the variable m has a new desired value 90 The corresponding optimiza tion problem is referred to as QP To solve this problem the resolve procedure makes use of the i
5. 11 These earlier descriptions however do not give any details of the algorithm although the incre mental deletion algorithm is described in 14 The current implementation is much improved in particular through the use of the active set method described in Section 4 1 Baraff 1 describes a quadratic optimization algorithm for solving linear constraints that arise in modelling physical sys tems Finally much of the work on constraint solvers has been in the logic programming and constraint logic program ming communities Current constraint logic programming languages such as CLP R 15 include efficient solvers for linear equalities and inequalities See 16 for a survey However these solvers use a refinement model of computa tion in which the values determined for variables are succes sively refined as the computation progresses but there is no notion as such of state and change As a result these systems are not so well suited for building interactive graphical appli cations 2 INCREMENTAL SIMPLEX As you see the subject of linear programming is sur rounded by notational and terminological thickets Both of these thorny defenses are lovingly cultivated by a co terie of stern acolytes who have devoted themselves to the field Actually the basic ideas of linear programming are quite simple Numerical Recipes 18 page 424 We now describe an incremental version of the simplex algo rithm adapted to the task at
6. 7 267 267 subject to lim 90 67 z Zp 150 4267 26 x 80 Oy EO s 110 426f 267 267 267 ee i 2 z z t 60 28 2 67 45 The tableau is no longer in basic feasible solved form since the constant of the row for s is negative even though s is supposed to be non negative Thus in general after updating the constants for the edit con straints the simplex tableau C s may no longer be in basic fea sible solved form since some of the constants may be nega tive However the tableau is still in basic form so we can still read a solution directly from it And since no coefficient has changed in particular in the optimization function the result ing tableau reflects an optimal but not feasible solution We need to find a feasible and optimal solution We could do so by adding artificial variables as we did when adding a con straint optimizing the sum of the artificial variables to find an initial feasible solution and then reoptimizing the original problem But we can do much better The process of moving from an optimal and infeasible solution to an optimal and fea sible solution is exactly the dual of normal simplex algorithm where we progress from a feasible and non optimal solution to feasible and optimal solution Hence we can use the dual simplex algorithm to find a feasible solution while staying op timal Solving the dual optimization
7. marker variable that is originally present only in the equa tion representing the constraint We can then identify the con straint s influence in the tableaux by looking for occurrences of that marker variable For inequality constraints the slack variable s added to make it an equality serves as the marker since s will originally occur only in that equation The equa tion representing a nonrequired equality constraint will have an error variable that can serve as a marker see Section 2 5 For required equality constraints we add a dummy nonneg ative variable to the original equation to serve as a marker which we never allow to enter the basis so that it always has value 0 In our running example then to allow the constraint 22m T r to be deleted incrementally we would add a dummy variable s3 resulting in 27 xj r 53 The simplex optimization routine checks for these dummy vari ables in choosing an entry variable and does not allow one to be selected For simplicity we didn t include this variable in the tableaux presented earlier Consider removing the constraint that z is 10 to the left of r The slack variable s which we added to the inequality to make it an equation records exactly how this equation has been used to modify the tableau We can remove the inequal ity by pivoting the tableau until s is basic and then simply drop the row in which it is basic In the tableau above s is al
8. problem starts from an infeasi ble optimal tableau of the form minimize e X72 djy subject to n m Nia Ti Ci Er Oa Yj where some c may be negative for rows with non negative basic variables infeasibility and each dj is non negative optimality The dual simplex algorithm selects an exit variable by find ing arow I with non negative basic variable x7 and negative constant cz The entry variable is the variable y 7 such that the ratio dj az 7 is the minimum of all d az where az is pos itive This ensures that when pivoting we stay at an optimal solution The pivot replacing y by 1 arj r cr Uy 444755 is performed as in the primal simplex algorithm Continuing the example above we select the exit variable so the only non negative basic variable for a row with negative constant We find that og has the minimum ratio since its co efficient in the optimization function is 0 so it will be the en try variable Replacing oF everywhere by 50 s2 267 26 Of we obtain the tableau minimize 30060 100267 99867 267 267 subject to Im 90 Oe aon try 100 Ss2 y 80 89 207 205 s 110 2s2 28 205 of 50 82 26f 2 L 40 S52 65 The tableau is feasible and of course still optimal and rep resents the solution m gt 90 2 100 z 4 80 So by sliding the midpoint further right the rightmost point hits the wall and the left point sl
9. simplex form equation by adding slack variables if it is an inequality Next we use the current tableau to substitute out all the basic variables This gives an equation e c where e is a linear expression If c is negative we multiply both sides by 1 so that the constant becomes non negative If e contains an unrestricted variable we use it to substitute for that variable and add the equation to the tableau above the line i e to Cy Otherwise we cre ate an non negative artificial variable a and add the equation a c e to the tableau below the line i e to C s and mini mize c e If the resulting minimum is not zero then the con straints are unsatisfiable Otherwise a is either parametric or basic If a is parametric the column for it can be simply re moved from the tableau If it is basic the row must have con stant 0 since we were able to achieve a value of 0 for our ob jective function which is equal to a If the row is just a 0 it can be removed Otherwise a 0 ba e where b 0 We can then pivot x into the basis using this row and remove the column for a 2 4 Incrementality Removing a Constraint We also want a method for incrementally removing a con straint from the tableaux After a series of pivots have been performed the information represented by the constraint may not be contained in a single row so we need a way to identify the constraint s influence in the tableaux To do this we use a
10. value f can be reduced if x is decreased So the 3rd constraint x gt 100 is moved out of the active set We now have the new approximate solution X xj the active set AW 1 and the optimization problem op minimize f subject to 2 m 2 r 0 To solve this problem we repeat the same procedure as for solving of The solution to this problem satisfies the equa tions 2 am 50 2 a 30 2x 2 2a x 70 2 2 m 2 70 0 oO These together with the constraint in oO have the solution x 50 30 70 This is the optimal solution to of and is also the optimal solution to the original problem QP zr Em Tr ipri os rae F b h h b F h F b F 0 50 100 Figure 3 Resolving the constraints using QOCA Now imagine that we have started to manipulate the diagram We have the weak constraints that x 30 and x 70 and the strong constraint that m 60 Reflecting this we change the first term in the function f to be 1000 m 60 denote it as f and the corresponding optimization problem as QP Starting from xg 50 30 70 which is the opti mal solution to QP an equality constrained problem of is formed oP is the same as oP except that they have dif ferent objective functions The solution to oP satisfies sim ilar linear equations to those of 1 These can be obtained by replacing the term 2 xm 50 in the first equation of
11. weak x 30 and weak x 70 so that x and x should stay where they are if possible There are two steps First we modify the tableau to reflect the new constraints we wish to solve Second we resolve the opti mization problem for this modified tableau Let us first examine how to modify the tableau to reflect the new values of the stay constraints This will not require re optimizing the tableau since we know that the new stay con straints are satisfied exactly Suppose the previous stay value for variable v was a and in the current solution v takes value 3 The current tableau contains the information that v a t and we need to modify this so that instead v B 6 There are two cases to consider a both T and are parameters or b one of them is basic In case a v must take the value a in the current solution since both 6 and 57 take the value 0 and v a 6 Hence B a and no changes need to be made In case b assume without loss of generality that 6 7 is ba sic In the original equation representing the stay constraint the coefficient for is the negative of the coefficient for 5 Since these variables occur in no other constraints this rela tion between the coefficients will continue to hold as we per form pivots In other words and 6 come in pairs any equation that contains will also contain 6 and vice versa Since 6 is assumed to be basic it occurs exa
12. 1 msec and resolving as the point moves 45 msec These tests were run using an implementation in OTI Smalltalk Version 4 0 running on a IBM Thinkpad 760EL laptop computer As these measurements are for implementations in different languages running on different machines they should not be viewed as any kind of head to head comparison Neverthe less they indicate that both algorithms are eminently practi cal for use with interactive graphical applications The QOCA toolkit has been employed in a number of applica tions The first application is part of an intelligent pen and pa per interface that contains a parser to incrementally parse dia grams drawn by the user using a stylus and that has a diagram editor that respects the semantics of the diagram by preserv ing the constraints recognized in the parsing process QOCA is used for both error correction in parsing and for diagram manipulation in the editor 7 A second QOCA application is for layout of trees and graphs in the presence of arbitrary lin ear arithmetic constraints and with suggested placements for some nodes 9 A Cassowary application currently being de veloped is a web authoring tool 5 in which the appearance of a page is determined by constraints from both the web au thor and the viewer Acknowledgments This project has been funded in part by the National Science Foundation under Grants IRI 9302249 and CCR 9402551 and by Object Technology International Alan
13. 50 years The most commonly used algorithm for solving it is the sim plex algorithm developed by Dantzig in the 1940s and there are now numerous variations of it Unfortunately however existing implementations of the simplex are not really suit able for UI applications The principal issue is incrementality In UI applications we need to solve similar problems repeatedly rather than solv ing a single problem once and to achieve interactive response times very fast incremental algorithms are needed There are two cases First when moving an object with a mouse or other input device we typically represent this interaction as a one way constraint relating the mouse position to the de sired x and y coordinates of a part of the figure For this case we must resatisfy the same collection of constraints differ ing only in the mouse location each time the screen is re freshed Second when editing an object we may add or re move constraints and other parts and we would like to make these operations fast by reusing as much of the previous so lution as possible The performance requirements are consid erably more stringent for the first case than the second Another issue is defining a suitable objective function The objective function in the standard simplex algorithm must be a linear expression but the objective functions for the locally error better weighted sum better and least squares better comparators are all non linear F
14. Borning s visit to Monash University and the University of Melbourne was sponsored in part by the Australian American Educational Foundation Fulbright Commission REFERENCES 1 D Baraff Fast contact force computation for nonpenetrating rigid bodies In SIGGRAPH 794 pages 23 32 2 A Borning R Anderson and B Freeman Benson Indigo A local propagation algorithm for inequality constraints In UIST 96 pages 129 136 Seattle Nov 1996 3 A Borning and B Freeman Benson The OTI constraint solver A constraint library for constructing interactive graph 10 11 12 13 14 15 16 17 18 19 20 21 ical user interfaces In Proc Constraint Programming 95 Springer Verlag LNCS Vol 910 Sep 1995 A Borning B Freeman Benson and M Wilson Constraint hierarchies Lisp and Symbolic Computation 5 3 223 270 Sep 1992 A Borning R Lin and K Marriott Constraints for the web In Proc ACM MULTIMEDIA 97 Nov 1997 To appear A Borning K Marriott P Stuckey and Y Xiao Solving lin ear arithmetic constraints for user interface applications Al gorithm details Tech report 97 06 01 Dept Computer Sci ence amp Engr Univ of Washington Seattle WA July 1997 S S Chok and K Marriott Automatic construction of user in terfaces from constraint multiset grammars In JEEE Sympo sium on Visual Languages pages 242 250 1995 R Fletcher Practical Method
15. Solving Linear Arithmetic Constraints for User Interface Applications Alan Borning and Kim Marriott Department of Computer Science Monash University Clayton Victoria 3168 AUSTRALIA borning marriott cs monash edu au ABSTRACT Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces such as requiring that one window be to the left of another requiring that a pane occupy the leftmost 1 3 of a window or preferring that an ob ject be contained within a rectangle if possible Current con straint solvers designed for UI applications cannot efficiently handle simultaneous linear equations and inequalities This is a major limitation We describe incremental algorithms based on the dual simplex and active set methods that can solve such systems of constraints efficiently KEYWORDS Linear constraints inequality constraints simplex algorithm 1 INTRODUCTION Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces in particular lay out and other geometric relations Inequality constraints in particular are needed to express relationships such as in side above below left of right of and over laps For example if we are designing a Web document we can express the requirement that figure1 be to the left of fig ure2 as the constraint figure1 rightSide lt figure2 leftSide It is important to be
16. able to express preferences as well as re quirements in a constraint system One use is to express a desire for stability when moving parts of an image things should stay where they were unless there is some reason for them to move A second use is to process potentially invalid user inputs in a graceful way For example if the user tries to move a figure outside of its bounding window it is reasonable for the figure just to bump up against the side of the window and stop rather than giving an error A third use is to balance conflicting desires for example in laying out a graph Permanent address Department of Computer Science amp Engineering University of Washington Box 352350 Seattle WA 98195 USA Peter Stuckey and Yi Xiao Department of Computer Science Department of Mathematics amp Statistics University of Melbourne Parkville Victoria 3052 AUSTRALIA pjs cs mu oz au yxiao maths mu oz au Efficient techniques are available for solving such constraints if the constraint network is acyclic However in trying to ap ply constraint solvers to real world problems we found that the collection of constraints was in fact often cyclic This sometimes arose when the programmer added redundant con straints the cycles could have been avoided by careful analysis However this is an added burden on the program mer Further it is clearly contrary to the spirit of the whole enterprise to require programmers to be constantly on gu
17. ants for the equations in Cy In either case the variable zo is said to be basic and the other variables in the equation are parameters A problem in basic feasible solved form de fines a basic feasible solution which is obtained by setting each parametric variable to 0 and each basic variable to the value of the constant in the right hand side For instance the following constraint is in basic feasible solved form and is equivalent to the problem above minimize 50 ixi 89 subject to Im 350 z 82 z 100 82 sy 90 p S9 The basic feasible solution corresponding to this basic feasi ble solved form is tm gt 50 zr 100 s gt 90 z gt 0 s2 gt 0 The value of the objective function with this solution is 50 2 2 Simplex Optimization We now describe how to find an optimum solution to a con straint in basic feasible solved form Except for the opera tions on the additional unrestricted variable tableau Cy the material presented in this subsection is simply the second phase of the standard two phase simplex algorithm The simplex algorithm finds the optimum by repeatedly look ing for an adjacent basic feasible solved form whose basic feasible solution decreases the value of the objective func tion When no such adjacent basic feasible solved form can be found the optimum has been found The underlying oper ation is called pivoting and involves exchanging a basic and a parametric varia
18. ard to avoid cycles and redundant constraints after all one of the goals in providing constraints is to allow programmers to state what relations they want to hold in a declarative fashion leaving it to the underlying system to enforce these relations For other applications such as complex layout problems with conflicting goals cycles seem unavoidable 1 1 Constraint Hierarchies and Comparators Since we want to be able to express preferences as well as requirements in the constraint system we need a specifica tion for how conflicting preferences are to be traded off Con straint hierarchies 4 provide a general theory for this In a constraint hierarchy each constraint has a strength The re quired strength is special in that required constraints must be satisfied The other strengths all label non required con straints A constraint of a given strength completely domi nates any constraint with a weaker strength In the theory a comparator is used to compare different possible solutions to the constraints and select among them As described in 2 it is important to use a metric rather than a predicate comparator for inequality constraints Thus plau sible comparators for use with linear equality and inequal ity constraints are locally error better weighted sum better and least squares better The least squares better compara tor strongly penalizes outlying values when trading off con straints of the same strength It is pa
19. asible This point is taken as the new approximate solution x and the violated constraints are added to the active set giving rise to a new optimization problem O 2 x is feasible with respect to the original problem QP It is directly taken as the new approximate solution x and we test to see it is also optimal QP This requires us to check if there exists a direction s at x such that a feasible in cremental step along s reduces f If such direction s ex ists then one constraint is taken out of the active set A to generate the direction s which results in a new optimiza tion problem O If no such direction exists we are finished since X is both feasible and optimal If the active set is modified the whole process is repeated un til the optimal solution is reached Consider our working example with the weak constraints that Im 50 z 30 and x 70 This gives rise to the mini mization problem QP minimize f m 50 a 30 r 70 subject to 1 2 ti r 0 2 a 2 gt 10 3 Sa S 100 4 t gt 0 Although it is obvious that m 50 x 30 2 70 or x 50 30 70 T is the optimal solution it is still instruc tive to see how the active set method computes this The ini tial guess and active set are read from the augmented simplex form tableux We start with an initial guess m 50 2 0 r 100 i e Xo 50 0 100 and constraints 1 3 and 4
20. be non negative it already takes its minimum value of 0 in the associated basic feasible solution Hence we are at an optimal solution In general the simplex algorithm applied to C s is described as follows We are given a problem in basic feasible solved form in which the variables 71 n are basic and the vari ables y1 Ym are parameters minimize e gt djy subject to Niti e GE aij yy A n m Nizi 2 OA A j 1 yj 2 0 Select an entry variable y 7 such that dy lt 0 An entry vari able is one that will enter the basis i e it is currently paramet ric and we want to make it basic Pivoting on such a variable can only decrease the value of the objective function If no such variable exists the optimum has been reached Now de termine the exit variable zz We must choose this variable so that it maintains basic feasible solved form by ensuring that the new c s are still positive after pivoting This is achieved by choosing an 27 so that c az 7 is a minimum element of the set ci aig aiz lt Oand1 lt i lt n If there were no 7 for which a z7 lt 0 then we could stop since the optimization problem would be unbounded and so would not have a minimum This is not an issue in our context since our optimization problems will always have a lower bound of 0 We proceed to choose x7 and pivot x out and replace it with yy to obtain the new basic feasible solution We con tinue this process until a
21. ble using matrix operations Thus by ad jacent we mean the new basic feasible solved form can be reached by performing a single pivot In our example increasing x from 0 will decrease the value of the objective function We must be careful as we cannot in crease the value of x indefinitely as this may cause the value of some other basic non negative variable to become nega tive We must examine the equations in C s The equation s 90 x s allows z to take at most a value of 90 as if x becomes larger than this then s would become neg ative The equations above the horizontal line do not restrict z Since whatever value x takes the unrestricted variables m and z can take a value to satisfy the equation In general we choose the most restrictive equation in C s and use it to eliminate z In the case of ties we arbitrarily break the tie In this example the most restrictive equation is s1 90 2 s9 Writing x as the subject we obtain x 90 s1 s2 We replace x everywhere by 90 s s and obtain minimize 5 51 s2 subject to Im 95 isi s2 zt 100 82 a 90 S S89 We have just performed a pivot having moved s out of the set of basic variables and replaced it by 27 We continue this process Increasing the value of s will in crease the value of the objective Note that decreasing s will also decrease the objective function value but as s is constrained to
22. bles efficiently and simply it was developed for implementing constraint logic programming languages 16 and we have adopted it here Essentially it uses two tableaux rather than one Equations containing at least one unre stricted variable will be placed in Cy the unrestricted vari able tableau while C s the simplex tableau contains those equations in which all variables are constrained to be non negative The simplex algorithm is used to determine an op timal solution for the equations in the simplex tableau ignor ing the unrestricted variable tableau for purposes of optimiza tion The equations in the unrestricted variable tableau are then used to determine values for its variables It is not difficult to write an arbitrary optimization problem over linear real equations and inequalities into augmented simplex form The first step is to convert inequalities to equa tions Each inequality of the form e lt r where e is a lin ear real expression and r is a number can be replaced with e s r A s gt 0 where sis a new non negative slack vari able For example the constraints for Figure 1 can be written as minimize m x subject to 22m UHtXLp a 10 s5 r zr s 100 0 lt Ti 51 82 We now separate the equalities into Cy and C s Initially all equations are in Cs We separate out the unrestricted vari ables into Cy using Gauss Jordan elimination To do this we select an equation in C s containing an unrestr
23. ctly once in an equation with constant c and further this equation also con tains the only occurrence of In the current solution v gt 3 6 4 c 0 O and since the equation v a 06 d7 holds 8 a c To replace the equation v a f 67 by v B we simply need to replace the constant cin this row by 0 Since there are no other occurrences of 6 5 and we have replaced the old equation with the new For our example to update the tableau for the new values for the stay constraints on x and x we simply set the constant of last equation the equation for of to 0 Now let us consider the edit constraints Suppose the pre vious edit value for v was a and the new edit value for v is 8 The current tableau contains the information that v a F 67 and again we need to modify this so that instead v 6 t 6 To do so we must replace every occurrence of by 8 a F 67 taking proper account of the coefficients of T and Again remember that F and 6 come in pairs If either of f and 57 is basic this simply involves appro priately modifying the equation in which they are basic Oth erwise if both are non basic then we need to change every equation of the form zti ci a aid e to zti ci a 8 a a t a l e Hence modifying the tableau to reflect the new values of edit and stay constraints involves only changing the constant val
24. h non required constraint with a weight so we obtain the objec tive function s 50 w a 30 w x 60 where s and w are weights so that the strong constraint is always strictly more important than solving any combination of weak constraints so that we find a locally error better or weighted sum better solution For the least squares better comparator the objective function is s m 50 w a 30 w a 60 In the presentation we will use s 1000 and w 1 Cassowary actually uses symbolic weights and a lexicographic ordering which ensures that strong constraints are always satisfied in preference to weak ones 6 However QOCA is not able to employ symbolic weights Unfortunately neither of these objective functions is linear and hence the simplex method is not applicable directly We now show how we can solve the problem using optimization algorithms based on the two alternate objective functions quasi linear optimization and quadratic optimization 3 CASSOWARY QUASI LINEAR OPTIMIZATION Cassowary finds either locally error better or weighted sum better solutions Since every weighted sum better solution is also a locally error better solution 4 the weighted sum part of the optimization comes automatically from the manner in which the objective function is constructed For Cassowary both the edit and the stay constraints will be represented as equations of the form v a F where
25. hand In the description we use a running example illustrated by the diagram in Figure 1 Xi Lm Lp G b F F H H H F H H H F 50 100 Figure 1 Simple constrained picture The constraints on the variables in Figure 1 are as follows m iS constrained to be the midpoint of the line from z to r and z is constrained to be at least 10 to the left of x All variables must lie in the range 0 to 100 Since x lt m lt r in any solution we simplify the problem by removing the re dundant bounds constraints However even with these sim plifications the resulting constraints have a cyclic constraint graph and cannot be handled by methods such as Indigo We can represent this using the constraints 22m Ut a 10 lt a tr lt 100 0 lt z Now suppose we wish to minimize the distance between m and z or in other words minimize m t 2 1 Augmented Simplex Form An optimization problem is in augmented simplex form if constraint C has the form Cy A Cs A Cr where Cy and C s are conjunctions of linear arithmetic equations and Cz is A x gt 0 z is a variable in Cs and the objective function f is a linear expression over variables in Cs The simplex algorithm does not itself handle variables that may take neg ative values so called unrestricted variables and imposes a constraint x gt Q0 on all variables occurring in its equa tions Augmented simplex form allows us to handle unre stricted varia
26. icted variable u and remove the equation from C s We then solve the equa tion for u yielding a new equation u e for some expression e We then substitute e for all remaining occurrences of u in C s Cy and f and place the equation u e in Cy The process is repeated until there are no more unrestricted vari ables in C s In our example the third equation can be used to substitute 100 s for x and the first equation can be used to substitute 50 ixi 82 for m giving minimize 50 z 82 subject to tm 50 2 82 tr 100 582 x 10 s 100 52 0 lt 2 81 82 The tableau shows Cy above the horizontal line and C s and C7 below the horizontal line From now on C7 will be omit ted any variable occurring below the horizontal line is im plicitly constrained to be non negative The simplex method works by taking a an optimization problem in basic feasible solved form a type of normal form and repeatedly applying matrix operations to obtain new basic feasible solved forms Once we have split the equations into Cy and C s we can ig nore Cy for purposes of optimization A augmented simplex form optimization problem is in basic feasible solved form if the equations are of the form Lo CH AX antn where the variable xg does not occur in any other equation or in the objective function If the equation is in C s c must be non negative However there is no such restriction on the const
27. ides right to satisfy the constraints The resulting diagram is shown at the bottom of Figure 2 To summarize incrementally finding a new solution for new input variables involves updating the constants in the tableaux to reflect the updated stay constraints then updat ing the constants to reflect the updated edit constraints and finally reoptimizing if needed In an interactive graphical ap plication when using the dual optimization method typically a pivot is only required when one part first hits a barrier or first moves away from a barrier The intuition behind this is that when a constraint first becomes unsatisfied the value of one of its error variables will become non zero and hence the variable will have to enter the basis when a constraint first becomes satisfied we can move one of its error variables out of the basis In the example pivoting occurred when the right point x came up against a barrier Thus if we picked up the mid point m with the mouse and smoothly slid it rightwards 1 pixel every screen refresh only one pivot would be required in moving from 50 to 95 This illustrates why the dual opti mization is well suited to this problem and leads to efficient resolving of the hierarchical constraints 4 QOCA QUADRATIC OPTIMIZATION Another useful way of comparing solutions to constraint hier archies is least squares better in which case we are interested in solving optimization problems of the following form
28. iour of the locally error better comparator in which the line grew until it bumped against the side 5 EMPIRICAL EVALUATION Our algorithms for incremental addition and deletion of equality and inequality constraints and for solving and re solving for the least square comparator using the QOCA al gorithm have been implemented as part of the QOCA C constraint solving toolkit The results are very satisfactory For a test problem with 300 constraints and 300 variables adding a constraint takes on average 1 5 msec deleting a con straint 1 6 msec the initial solve 12 msec and subsequent re solving as the point moves 4 5 msec For a larger problem with 900 constraints and variables adding a constraint takes on average 9 7 msec deleting a constraint 17 msec the ini tial solve 120 msec and subsequent resolving as the point moves 67 msec These tests were run a sun4m sparc running SunOS 5 4 Running Cassowary on the same problems for the 300 con straint problem adding a constraint takes on average 38 msec including the initial solve deleting a constraint 46 msec and resolving as the point moves 15 msec Stay and edit constraints are represented explicitly in this implementation so there were also stay constraints on each variable plus two edit constraints for a total of 602 constraints For the 900 constraint problem adding a constraint takes on av erage 98 msec again including the initial solve deleting a constraint 15
29. n optimum is reached 2 3 Incrementality Adding a Constraint We now describe how to add the equation for a new constraint incrementally This technique is also used in our implementa tions to find an initial basic feasible solved form for the origi nal simplex problem by starting from an empty constraint set and adding the constraints one at a time As an example suppose we wish to ensure the additional con straint that the midpoint sits in the centre of the screen This is represented by the constraint zm 50 If we substitute for each of the basic variables only m in this constraint we obtain the equation 45 ts s2 0 In order to add this constraint straightforwardly to the tableau we create a new non negative variable a called an artificial variable This is simply an incremental version of the operation used in the first phase of the two phase simplex algorithm We let a 45 51 s be added to the tableau clearly this gives a tableau in basic feasible solved form and then minimize the value of a If a takes the value 0 then we have obtained a so lution to the problem with the added constraint and we can then eliminate the artificial variable altogether since it is a pa rameter and hence takes the value 0 This is the case for our example the resulting tableau is tm 50 t 100 s y 0 82 Ss 90 285 In general to add a new required constraint to the tableau we first convert it to an augmented
30. nformation from the previous solve QP while applying the active set method to QP When resolving it is important to notice that if we start from the solution for the previous problem QP i e xo 59 98 39 98 79 98 then the solution to the correspond ing equality constrained problem of minimize f3 subject to 27 z x 0 can be easily obtained In fact one can just replace the desired value 60 for zm in 2 by its new desired value 90 which leads to the optimal solution to o as xj 89 9202 69 9202 109 9202 T If the desired value does not change too much it is quite likely that x is also optimal for QP Unfortunately this is not the case for this example since x violates the 3rd constraint z gt 100 Choos ing a 0 1 to be as big as possible while still ensuring that X1 Xo XG Xo is feasible we have a 0 6687 and X Xo a x Xo as the new approximate solution at which the 3rd constraint becomes active By solving the cor responding equality constrained problem QP minimize f3 subject to 27 21 2 0 r 100 the optimal solution to Q P3 is found to be zm 89 9003 x 79 8007 x 100 Figure 3 shows the effect of moving the horizontal line with the least squares comparator With this comparator the line moves right maintaining the same length until it hits the right boundary at which point it starts to compress This contrasts with the behav
31. ortunately techniques have been developed in the operations research community for handling these cases which we adopt here For the first two comparators the objective functions are almost linear while the third comparator gives rise to a quadratic optimiza tion problem Finally a third issue is accommodating variables that may take on both positive and negative values which in general is the case in UI applications The standard simplex algorithm requires all variables to be non negative Here we adopt effi cient techniques developed for implementing constraint logic programming languages 1 3 Overview We present algorithms for incrementally solving linear equal ity and inequality constraints for the three different compara tors described above In Section 2 1 we give algorithms for incrementally adding and deleting required constraints with restricted and unrestricted variables from a system of con straints kept in augmented simplex form a type of solved form In Section 3 1 we give an algorithm Cassowary based on the dual simplex for incrementally solving hierarchies of constraints using the locally error better or weighted sum better comparators when a constraint is added or an object is moved while in Section 4 we give an algorithm QOCA based on the active set method for incrementally solving hi erarchies of constraints using the least squares better com parator Both of our algorithms have been implemented
32. puting Cambridge 1989 M Sannella J Maloney B Freeman Benson and A Born ing Multi way versus one way constraints in user interfaces Experience with the DeltaBlue algorithm Software Practice and Experience 23 5 529 566 May 1993 I Sutherland Sketchpad A man machine graphical commu nication system In Proc Spring Joint Computer Conference pages 329 346 IFIPS 1963 B Vander Zanden An incremental algorithm for satisfying hierarchies of multi way dataflow constraints ACM TOPLAS 18 1 30 72 Jan 1996
33. r and 6 are non negative variables representing the devi ation of v from the desired value a If the constraint is satis fied both f and 6 will be 0 Otherwise r will be positive and will be 0 if v is too big or vice versa if v is too small Since we want f and to be 0 if possible we make them part of the objective function with larger coefficients for the error variables for stronger constraints Translating the constraints strong m 50 weak x 30 and weak x 60 that arise from the edit and stay constraints we obtain lm 50 067 65 x 30467 6 Lr 6046 z 0 lt OF z Ot 0 Or r The objective function to satisfy the non required constraints can now be restated as minimize 100007 100057 67 65 Of 65 An optimal solution of this problem can be found using the simplex algorithm and results in a tableau minimize 10 10028 99867 207 267 subject to Pin 50 n zn ty 70 268 267 Xyp 30 67 O s 30 2 7 202 20 P20 s2 30 20k 2 z Og 10 28 26 i 6 65 This corresponds to the solution m 1 50 2 gt 30 r gt 70 illustrated in Figure 1 Notice that the weak con straint on is not satisfied 3 1 Incrementality Resolving the Optimization Problem Now suppose the user moves the mouse which is editing m to x 60 We wish to solve a new problem with constraints strong Xm 60 and
34. ready basic and so removing it simply means dropping the row in which it is basic obtaining Im 50 t 100 s t 0 582 If we wanted to remove this constraint from the tableau before adding m 50 i e the final tableau given in Section 2 2 s is a parameter We make s basic by treating it as an entry variable determining the most restrictive equation and using that equation to pivot s into the basis See 6 for details We then remove the row Here the row x 90 s1 s2 is the most constraining equation Pivoting to let s enter the basis and then removing the row in which it is basic we obtain 50 32 4s 100 582 Lm r 2 5 Handling Non Required Constraints Suppose the user wishes to edit m in the diagram and have x and x weakly stay where they are This adds the non required constraints m edit x stay and x stay Suppose further that we are trying to move m to position 50 and that x and x are currently at 30 and 60 respectively We are thus imposing the constraints strong m 50 weak x 30 and weak x 60 There are two possible translations of these non required constraints to an objective function depending on the comparator used For locally error better or weighted sum better we can sim ply add the errors of the each constraint to form an objective function Consider the constraint m 50 We define the error as m 50 We need to combine the errors for eac
35. rticularly suited to tasks such as laying out a tree a graph or a collection of win dows where there are inherently conflicting preferences for example that all the nodes in the depiction of a graph have some minimum spacing and that edge lengths be minimized Locally error better on the other hand is a more permissive comparator in that it admits more solutions to the constraints In fact any least squares better or weighted sum better so lution is also a locally error better solution 4 It is thus easier to implement algorithms to find a locally error better solution and in particular to design hybrid algorithms that include subsolvers for simultaneous equations and inequali ties and also subsolvers for nonnumeric constraints 3 Since each of these different comparators is preferable in certain sit uations we give algorithms for each 1 2 Adapting the Simplex Algorithm Linear programming is concerned with solving the follow ing problem Consider a collection of n real valued vari ables 1 Zn each of which is constrained to be non negative x gt Ofor 1 lt i lt n There are m linear equality or inequality constraints over the 7 each of the form az antn b az antn lt b or ati anin b Given these constraints we wish to find values for the x that minimizes or maximizes the value of the objective function c dizi t dnin This problem has been heavily studied for the past
36. s of Optimization Wiley 1987 W He and K Marriott Constrained graph layout In Graph Drawing 96 Springer Verlag LNCS Vol 1190 pages 217 232 R Helm T Huynh C Lassez and K Marriott A linear con straint technology for interactive graphic systems In Graphics Interface 92 pages 301 309 1992 R Helm T Huynh K Marriott and J Vlissides An object oriented architecture for constraint based graphical editing In Proc Third Eurographics Workshop on Object oriented Graphics Champery Switzerland Oct 1992 H Hosobe S Matsuoka and A Yonezawa Generalized local propagation A framework for solving constraint hierarchies In Proc Constraint Programming 96 Springer Verlag LNCS Vol 1118 Aug 1996 S E Hudson and I Smith SubArctic UI toolkit user s manual Tech report College of Computing Georgia Tech 1996 T Huynh and K Marriott Incremental constraint deletion in systems of linear constraints Information Processing Letters 55 111 115 1995 J Jaffar S Michaylov P Stuckey and R Yap The CLP R language and system ACM TOPLAS 14 3 339 395 July 1992 K Marriott and P Stuckey Introduction to Constraint Logic Programming MIT Press 1997 In preparation B A Myers The Amulet user interface development environ ment In ACM CHI 96 Conference Companion Apr 1996 W H Press B P Flannery S A Teukolsky and W T Vetter ling Numerical Recipes The Art of Scientific Com
37. ts of the original equality constraints plus those inequality constraints that are tight in other words those inequalities that are currently required to be satisfied as equalities The other inequalities are ignored for the moment Essentially each optimization problem O can be treated as an unconstrained quadratic optimization problem denoted by U To obtain U we rewrite the equality constraints in O in basic feasible solved form and then eliminate all basic vari ables in the objective function f The optimal solution is the point at which all of the partial derivatives of f equal zero The problem U can be solved easily since we are dealing with a convex quadratic function f and so its derivatives are linear As a result to solve U we need only solve a system of linear equations over unconstrained variables In more detail in the active set method we assume at each stage that a feasible initial guess Xo z1 n is avail able as well as the corresponding active set A Assume that we have just solved the optimization problem Op and let its solution be xj We face the following two possibilities when determining the new approximate solution xj 1 xg is feasible with respect to the constraints in Oo but it violates some inequality constraints in QP that are not in the current active set A In this case a scalar 0 1 is selected such that it is as large as possible and the point Xo a x xo is fe
38. ues in some equations The modifications for stay constraints always result in a tableau in basic feasible solved form since it never makes a constant become negative In contrast the modifications for edit constraints may not To return to our example suppose we pick up m with the mouse and move it to 60 Then we have that a 50 and 8 60 so we need to add 10 times the coefficient of or to the constant part of every row The modified tableau after the updates for both the stays and edits is minimize 20 10020 9986 26 207 subject to fm 60 zn r 90 26 205 i t 30 Og z s 50 26 267 28i 26 s2 10 20 2 3 z 20 4267 2 z i z 065 Clearly it is feasible and already in optimal form and so we have incrementally resolved the problem by simply modify ing constants in the tableaux The new tableaux give the so lution m gt 60 2 gt 30 2 90 So sliding the mid point rightwards has caused the right point to slide rightwards as well but twice as far The resulting diagram is shown at the top of Figure 2 Suppose we now move m from 60 to 90 The modified tableau is x Lm Lp G 6 i a a BoSkes PSS poopooRSops Shs 0 50 100 wy Em bassssersrrnntttnt gt Er e 4 cane ieiaiiaar Seana teen tae a a o b oR bebo PS 0 50 100 Figure 2 Resolving the constraints minimize 60 10026 998
Download Pdf Manuals
Related Search