Constraint Satisfaction Problems with Order-Sorted Domains

约束也是一种幸福1000字作文英文回答：Constraints are indeed a form of happiness. At first glance, it may seem contradictory to associate constraints with happiness. After all, constraints imply limitationsand restrictions, which may hinder one's freedom and autonomy. However, upon closer examination, it becomesclear that constraints can actually contribute to a senseof contentment and fulfillment.Constraints provide structure and guidance in our lives. They set boundaries and establish rules, which help us navigate through the complexities of life. Without constraints, we would be lost and overwhelmed by theinfinite possibilities and choices available to us. Constraints act as a compass, guiding us towards what is important and valuable.Moreover, constraints foster discipline and self-control. By adhering to constraints, we develop the ability to resist temptations and make responsible decisions. This self-discipline brings a sense of achievement and pride, leading to a deeper satisfaction and happiness. It allows us to overcome obstacles and achieve our goals, knowingthat we have exercised restraint and stayed on the right path.Constraints also encourage creativity and innovation. When faced with limitations, we are forced to think outside the box and find alternative solutions. Constraints push us to explore new ideas and approaches, leading to breakthroughs and advancements. The challenges posed by constraints stimulate our minds and ignite our creativity, ultimately leading to a greater sense of accomplishment and happiness.In addition, constraints promote gratitude and appreciation. When we are aware of the limitations imposed on us, we learn to value what we have and cherish the opportunities available to us. Constraints remind us of the privileges and blessings we enjoy, fostering a sense ofgratitude and contentment. This gratitude enhances our overall well-being and contributes to our happiness.In conclusion, constraints are not necessarily detrimental to happiness. On the contrary, they can be a source of contentment and fulfillment. Constraints provide structure, foster discipline, encourage creativity, and promote gratitude. Embracing and navigating within constraints can lead to a deeper sense of happiness and satisfaction in life.中文回答：约束确实是一种幸福。

EUROGRAPHICS Workshop on...(2004),pp.1–10M.-P.Cani and M.Slater(Guest Editors)Can Machines Interpret Line Drawings?P.A.C.Varley,1R.R.Martin2and H.Suzuki11Department of Fine Digital Engineering,The University of Tokyo,Tokyo,Japan2School of Computer Science,Cardiff University,Cardiff,Wales,UKKeywordsSketching,Line Drawing Interpretation,Engineering De-sign,Conceptual Design1.IntroductionCan computers interpret line drawings of engineering ob-jects?In principle,they cannot:any line drawing is the 2D representation of an infinite number of possible3D ob-jects.Fortunately,a counter-argument suggests that comput-ers should be able to interpret line drawings.Human engi-neers use line drawings to communicate shape in the clear expectation that the recipient will interpret the drawing in the way the originator intended.It is believed[Lip98,Var03a] that human interpretation of line drawings is a skill which can be learned.If such skills could be translated into algo-rithms,computers could understand line drawings.There are good reasons why we want computers to in-terpret line drawings.Studies such as Jenkins[Jen92]have shown that it is common practice for design engineers to sketch ideas on paper before entering them into a CAD pack-age.Clearly,time and effort could be saved if a computer could interpret the engineer’s initial concept drawings as solid models.Furthermore,if this conversion could be done within a second or two,it would give helpful feedback,fur-ther enhancing the designer’s creativity[Gri97].The key problem is to produce a model of the3D object the engineer would regard as the most reasonable interpreta-tion of the2D drawing,and to do so quickly.While there are infinitely many objects which could result in drawings cor-responding to e.g.Figures1and2,in practice,an engineer would be in little doubt as to which was the correct interpre-tation.For this reason,the problem is as much heuristic as geometric:it is not merely tofind a geometrically-realisable solid which corresponds to the drawing,but tofind the one which corresponds to the engineer’s expectations.We suggest the following fully automatic approach,re-quiring no user intervention;our implementation verifies its utility for many drawings of polyhedral objects.(In a com-panion paper[VTMS04],we summarise an approach for in-terpreting certain drawings of curved objects with minimal user intervention.)submitted to EUROGRAPHICS Workshop on (2004)2P .Varley &R.Martin &H.Suzuki /Can Machines Interpret LineDrawings?Figure 1:Trihedral Draw-ing[Yan85]Figure 2:Non-Trihedral Drawing [Yan85]•Convert the engineer’s original freehand sketch to a line drawing.This is described in Section 3.•Determine the frontal geometry of the object.The three most crucial aspects of this are:–Label the lines in the drawing as convex,concave,or occluding.See Section 4.–Determine which pairs of lines in the drawing are in-tended to be parallel in 3D.See Section 5.–Inflate the drawing to 212D”).In a frontal geometry,everything visible in the nat-ural line drawing is given a position in 3D space,but the oc-cluded part of the object,not visible from the chosen view-point,is not present.A polyhedron is trihedral if three faces meet at each ver-tex.It is extended trihedral [PLVT98]if three planes meet at each vertex (there may be four or more faces if some are coplanar).It is tetrahedral if no more than four faces meet at any vertex.It is a normalon if all edges and face normals are aligned with one of three main perpendicular axes.Junctions of different shapes are identified by letter:junc-tions where two lines meet are L-junctions ,junctions of three lines may be T-junctions ,W-junctions or Y-junctions ,and junctions of four lines may be K-junctions ,M-junctions or X-junctions .Vertex shapes follow a similar convention:for example,when all four edges of a K-vertex are visible,the drawing has four lines meeting at a K -junction.When reconstructing an object from a drawing,we take the correct object to be the one which a human would decide to be the most plausible interpretation of the drawing.3.Convert Sketch to Line DrawingFor drawings of polyhedral objects,we believe it to be most convenient for the designer to input straight lines directly,and our own prototype system,RIBALD,includes such an interface.However,it could be argued that freehand sketch-ing is more “intuitive”,corresponding to a familiar interface:pen and paper.Several systems exist which are capable of converting freehand sketches into natural line drawings—see e.g.[ZHH96],[Mit99],[SS01].4.Which Lines are Convex/Concave?Line labelling is the process of determining whether each line in the drawing represents a convex,a concave,or an oc-cluding edge.For drawings of trihedral objects with no hole loops,the line labelling problem was essentially solved by Huffman [Huf71]and Clowes [Clo70],who elaborated the catalogue of valid trihedral junction labels.This turns line labelling into a discrete constraint satisfaction problem with 1-node constraints that each junction must have a label in the catalogue and 2-node constraints that each line must have the same label throughout its length .The Clowes-Huffman catalogue for L -,W -and Y -junctions is shown in Figure 3;+indicates a convex edge,−indicates a concave edge,and an arrow indicates an occluding edge with the occluding face on the right-hand side of the arrow.In trihedral objects,T -junctions (see Figure 4)are always occluding.For trihedral objects,algorithms for Clowes-Huffman line labelling,e.g.those of Waltz [Wal72]and Kanatani [Kan90],although theoretically taking O (2n )time,are usually O (n )insubmitted to EUROGRAPHICS Workshop on (2004)P .Varley &R.Martin &H.Suzuki /Can Machines Interpret Line Drawings?3+-+-+-+++---Figure 3:Clowes-HuffmanCatalogueFigure 4:Occluding T -Junctionspractice [PT94].It is believed that the time taken is more a function of the number of legal labellings than of the algo-rithm,and for trihedral objects there is often only a single legal labelling.For example,Figure 1has only one valid la-belling if the trihedral (Clowes-Huffman)catalogue is used.Extending line labelling algorithms to non-trihedral nor-malons is fairly straightforward [PLVT98].The additional legal junction labels are those shown in Figure 5.Note,how-ever,that a new problem has been introduced:the new T -junctions are not occluding.-+-+-+Figure 5:Extended Trihedral JunctionsExtension to the 4-hedral general case is less straight-forward.The catalogue of 4-hedral junction labels is much larger [VM03]—for example,Figure 6shows just the possi-bilities for W -junctions.Because the 4-hedral catalogue isno+-+-+-Figure 6:4-Hedral W -Junctionslonger sparse ,there are often many valid labellings for each drawing.Non-trihedral line labelling using the previously mentioned algorithms is now O (2n )in practice as well as in theory,and thus too slow.Furthermore,choosing the best labelling from the valid ones is not straightforward either,although there are heuristics which can help (see [VM03]).Instead,an alternative labelling method is to use a relax-ation bel probabilities are maintained for each line and each junction;these probabilities are iteratively up-dated.If a probability falls to 0,that label is removed;if a probability reaches 1,that label is chosen and all other la-bels are removed.In practice,this method is much faster—labels which are possible but very unlikely are removed quickly by relaxation,whereas they are not removed at all by combinatorial algorithms.However,relaxation methods are less reliable (the heuristics developed for choosing between valid labellings when using combinatorial methods are rea-sonably effective).In test we performed on 535line draw-ings [Var03b],combinatorial labelling labelled 428entirely correctly,whereas relaxation labelling only labelled 388en-tirely correctly.The most serious problem with either approach is that in treating line labelling as a discrete constraint satisfaction problem,the geometry of the drawing is not taken into ac-count,e.g.the two drawings in Figure 7are labelled the same.The problems created by ignoring geometrybecomeFigure 7:Same Topologymuch worse in drawings with several non-trihedral junctions (see [VSM04]),and for these,other methods are required.A new approach to labelling outlined in that paper and subsequently developed further [VMS04]makes use of an idea previously proposed for inflation [LB90]:•Assign relative i ,j ,k coordinates to each junction by as-suming that distances along the 2D axes in Figure 8cor-respond to 3D distances along spatial i ,j ,k axes.•Rotate the object from i ,j ,k to x ,y ,z space,where the lat-ter correspond to the 2D x ,y axes and z is perpendicular to the plane of the drawing.•Find the 3D equation for each planar region using vertex x ,y ,z coordinates.•For each line,determine from the equations of the two faces which meet the line whether it is convex,concave or occluding (if there is only one face,the line is occluding).submitted to EUROGRAPHICS Workshop on (2004)4P .Varley &R.Martin &H.Suzuki /Can Machines Interpret LineDrawings?+k-k+i-i+j-jFigure 8:Three Perpendicular Axes in 2DOn its own,this method does not work well:e.g.it is dif-ficult to specify a threshold distance d between two faces such that a distance greater than d corresponds to a step,and hence an occluding line,while if the distance is less than d the planes meet and the line is convex or concave.However,using the predictions made by this method as input to a re-laxation labelling algorithm provides far better results than using arbitrary initialisation in the same algorithm.This idea can be combined with many of the ideas in Sec-tion 6when producing a provisional geometry.Various vari-ants of the idea have been considered (see [VMS04]),partic-ularly with reference to how the i ,j ,k axes are identified in a 2D drawing,without as yet any firm conclusions as to which is best overall.Another strength is that the idea uses the relaxation labeller to reject invalid labellings while collat-ing predictions made by other approaches.This architecture allows additional approaches to labelling,such as Clowes-Huffman labelling for trihedral objects,to make a contribu-tion in those cases where they are useful [VMS04].Even so,the current state-of-the-art only labels approxi-mately 90%of non-boundary edges correctly in a represen-tative sample of drawings of engineering objects [VMS04].Note that any approach which uses catalogue-based la-belling can only label those drawings whose vertices are in a catalogue—it seems unlikely that 7-hedral and 8-hedral ex-tended K-type vertices of the type found in Figure 9willbeFigure 9:Uncatalogued Verticescatalogued in the near future.In view of this,one must ques-tion whether line labelling is needed.Humans are skilled at interpreting line drawings,and introspection tells us that line labelling is not always a part of this process—it may evenbe that humans interpret the drawing first,and then (if nec-essary)determine which lines are convex,concave and oc-cluding from the resulting mental model.Our investigations indicate that line labelling is needed,at least at present.We are investigating interpreting line draw-ings without labelling,based on identifying aspects of draw-ings which humans are known or believed to see quickly,such as line parallelism [LS96],cubic corners [Per68]and major axis alignment [LB90].Current results are disappoint-ing.Better frontal geometry can be obtained if junction la-bels are available.More importantly,the frontal geometry is topologically unsatisfactory.Distinguishing occluding from non-occluding T -junctions without labelling information is unreliable,and as a result,determination of hidden topology (Section 8)is unlikely to be successful.5.Which Lines are Parallel?Determining which lines in a drawing are intended to be par-allel in 3D is surprisingly difficult.It is,for example,obvious to a human which lines in the two drawings in Figure 10are intended to be parallel and which are not,but determining this algorithmically presentsproblems.Figure 10:Which Lines are Parallel?Sugihara [Sug86]attempted to define this problem away by using a strict definition of the general position rule:the user must choose a viewpoint such that if lines are parallel in 2D,the corresponding edges in 3D must be parallel.This makes no allowance for the small drawing errors which in-evitably arise in a practical system.Grimstead’s “bucketing”approach [Gri97],grouping lines with similar orientations,works well for many draw-ings,but fails for both drawings in Figure 10.Our own “bundling”approach [Var03a],although somewhat more re-liable,fares no better with these two drawings.The basic idea used in bundling is that edges are parallel if they look parallel unless it can be deduced from other information that they cannot be parallel.The latter is problematic for two rea-sons.Firstly,if ‘other information’means labelling,iden-tification of parallel lines must occur after labelling,limit-ing the system organisation for computing frontal geome-try.Secondly,to cover increasingly rare exceptional cases,we must add extra,ever more complex,rules for deducing which lines may or may not be parallel.This is tedious andsubmitted to EUROGRAPHICS Workshop on (2004)P.Varley&R.Martin&H.Suzuki/Can Machines Interpret Line Drawings?5 rapidly reaches the point of diminishing returns.For exam-ple,a rule which can deduce that the accidental coincidencein Figure11should not result in parallel lines would be bothcomplicated to implement and of no use in many other cases.**Figure11:Accidental CoincidenceFurthermore,there are also cases where it is far from cleareven to humans which edges should be parallel in3D(edgesA,B,C and D in Figure12are a case in point).ABCDFigure12:Which Edges Should Be Parallel?In view of these problems,more recent approaches tofrontal geometry(e.g.[VMS04])simply ignore the possi-bility that some lines which appear parallel in2D cannot infact be parallel in3D.Initially,it is assumed that they areparallel;this information is then re-checked after inflation.6.Inflation to212D by assigning z-coordinates(depth coordinates)to eachvertex,producing a frontal geometry.The approach taken here is the simplest:we use compliance functions[LS96]to generate equations linear in vertex depth coordinates,and solve the resulting linear least squares problem.Many com-pliance functions can be translated into linear equations in z-coordinates.Of these,the most useful are:Cubic Corners[Per68],sometimes called corner orthogo-nality,assumes that a W-junction or Y-junction corresponds to a vertex at which three orthogonal faces meet.See Fig-ure13:the linear equation relates depth coordinates z V and z A to angles F and G.Nakajima[Nak99]reports successful creation of frontal geometry solely by using a compliance function similar to corner orthogonality,albeit with a limited set of test drawings in which orthogonality predominates. Line Parallelism uses two edges assumed to be parallel in 3D.The linear equation relates the four z-coordinates of theVA BCEFGVABCEFGFigure13:Cubic Cornersvertices at either end of the two edges.Line parallelism is not,by itself,inflationary:there is a trivial solution(z=0 for all vertices).Vertex Coplanarity uses four vertices assumed to be coplanar.The linear equation relating their z-coordinates is easily obtained from2D geometry.Vertex coplanarity is also not,by itself,inflationary,having the trivial solution z=0 for all vertices.General use of four-vertex coplanarity is not recommended(Lipson[Lip98]notes that if three vertices on a face are collinear,four-vertex coplanarity does not guar-antee a planar face).However,it is invaluable for cases like those in Figure14,to link vertices on inner and outer face loops:without it the linear system of depth equations would be disjoint,with infinitely many solutions.**Figure14:Coplanar VerticesLipson and Shpitalni[LS96]list the above and several other compliance functions;we have devised the following. Junction-Label Pairs[Var03a]assumes that pairs of junc-tions with identified labels have the same depth implications they would have in the simplest possible drawing contain-ing such a pair.An equation is generated relating the vertex depths at each end of the line based on the junction labels of those vertices.For example,see Figure15:this pair of junc-tion labels can be found in an isometric drawing of a cube, and the implication is that the Y-junction is nearer to the viewer than the W-junction,with the ratio of2D line length to depth change being√6P .Varley &R.Martin &H.Suzuki /Can Machines Interpret LineDrawings?Figure 15:Junction La-bel Pair *Figure 16:Incorrect Infla-tion?paper.Although it occasionally fails to determine correctly which end of a line should be nearer the viewer,such failures arise in cases like the one in Figure 16where a human would also have difficulty.The only systematic case where using a linear system of compliance functions fails is for Platonic and Archimedean solids,but a known special-case method (Marill’s MSDA [Mar91])is successful for these.In order to make the frontal geometry process more ro-bust when the input information (especially line labelling)is incorrect,we have experimented with two approaches to inflation which do without some or all of this information.The first is the ‘preliminary inflation’described in Sec-tion 4:find the i ,j ,k axes in the drawing,inflate the object in i ,j ,k space,then determine the transformation between i ,j ,k and x ,y ,z spaces.This requires parallel line information (to group lines along the i ,j ,k axes).Where such information is misleading,the quality of inflation is unreliable,but this is not always a problem,e.g.the left-hand drawing in Figure 10is labelled correctly despite incorrect parallel line informa-tion.Once (i)a drawing has been labelled correctly and (ii)there is reason to suppose that the parallel line information is unreliable,better-established inflation methods can be used to refine the frontal geometry.However,the right-hand draw-ing is one of those which is not labelled correctly,precisely because of the misleading parallel line information.A second promising approach,needing further work,at-tempts to emulate what is known or hypothesised about hu-man perception of line drawings.It allocates merit figures to possible facts about the drawing;these,and the geometry which they imply,are iteratively refined using relaxation:•Face-vertex coplanarity corresponds to the supposition that vertices lie in the plane of faces.We have already noted the difficulty of distinguishing occluding from non-occluding T -junctions;to do so,we must at some time decide which vertices do lie in the plane of a face.•Corner orthogonality ,which was described earlier.At least one inflationary compliance function is required,and this one has been found reliable.Although limited in prin-ciple,corner orthogonality is particularly useful in prac-tice as cubic corners are common in engineering objects.•Major axis alignment is the idea described above of using i ,j ,k axes.This is also an inflationary compliance func-tion.It is newer than corner orthogonality,and for this reason considered less reliable.However,unlike cornerorthogonality (which can fail entirely in some circum-stances),major axis alignment does always inflate a draw-ing,if not always entirely correctly.•Line parallelism is useful for producing ‘tidy’output (e.g.to make lines terminating in occluding T -junctions paral-lel in 3D to other lines with similar 2D orientation).How-ever,the main reason for its inclusion here is that it also produces belief values for pairs of lines being parallel as a secondary output,solving the problem in Section 5.•Through lines correspond to the requirement that a contin-uous line intercepted by a T -junction or K -junction corre-sponds to a single continuous edge of the object.A third,simpler,approach assumes that numerically cor-rect geometry is not required at this early stage of pro-cessing,and identifying relative depths of neighbouring ver-tices is sufficient.Schweikardt and Gross’s [SG00]work,al-though limited to objects which can be labelled using the Clowes-Huffman catalogue,and not extending well to non-normalons,suggests another possible way forward.7.Classification and SymmetryIdeally,one method should work for all drawings of poly-hedral objects;identification of special cases should not be necessary.However,the state-of-the-art is well short of this ideal—in practice it is useful to identify certain frequent properties of drawings and objects.Identification of planes of mirror symmetry is particularly useful.Knowledge of such a symmetry can help both to construct hidden topol-ogy (Section 8)and to beautify the resulting geometry (Sec-tion 9).Identification of centres of rotational symmetry is less useful [Var03a],but similar methods could be applied.The technique adopted is straightforward:for each possi-ble bisector of each face,create a candidate plane of mirror symmetry,attempt to propagate the mirror symmetry across the entire visible part of the object,and assess the results us-ing the criteria of (i)to what extent the propagation attempt succeeded,(ii)whether there is anything not visible which should be visible if the plane of mirror symmetry were a genuine property of the object,and (iii)how well the frontal geometry corresponds to the predicted mirror symmetry.Classification of commonly-occurring types of objects (examples include extrusions,normalons,and trihedral ob-jects)is also useful [Var03a],as will be seen in Section 8.One useful combination of symmetry and classification is quite common in engineering practice (e.g.see Figures 1and 2):a semi-normalon (where many,but not all,edges and face normals are aligned with the major axes)also having a dominant plane of mirror symmetry aligned with one of the object’s major axes [Var03a].The notable advantage of this classification is that during beautification (Section 9)it pro-vides constraints on the non-axis-aligned edges and faces.We recommend that symmetry detection and classifica-submitted to EUROGRAPHICS Workshop on (2004)P.Varley&R.Martin&H.Suzuki/Can Machines Interpret Line Drawings?7tion should be performed after creation of the frontal geom-etry.Detecting candidate symmetries without line labels is unreliable,and assessing candidate symmetries clearly ben-efits from the3D information provided by inflation.The issue is less clear for classification.Some classifications (e.g.whether the object is a normalon)can be done directly from the drawing,without creating the frontal geometryfirst. However,others cannot,so for simplicity it is preferable to classify the object after creating its frontal geometry.8.Determine Hidden TopologyOnce the frontal geometry has been determined,the next stage of processing is to add the hidden topology.The method is essentially that presented in[VSMM00]:firstly, add extra edges to complete the wireframe,and then add faces to the wireframe to compete the object,as follows:While the wireframe is incomplete:•Project hypothesised edges from each incomplete vertex along the appropriate axes•Eliminate any edges which would be visible at their points of origin•Find locations where the remaining edges intersect,as-signing meritfigures according to how certain it is that edges intersect at this location(e.g.an edge intersecting only one other edge has a higher meritfigure than an edge has potential intersections with two or more other edges)•Reduce the merit for any locations which would be visible (these must be considered,as drawing errors are possible)•Choose the location at which the merit is greatest •Add a vertex at this location,and the hypothesised edges meeting at this location,to the known object topology The process of completing the wireframe topology varies in difficulty according to the type of object drawn.We il-lustrate two special-case object classes,extrusions and nor-malons,and the general case.In some cases(e.g.if the ob-ject is symmetrical or includes a recognised feature),more than one vertex can be added in one iteration,as described in[Var03a].Such cases increase both the speed and reliabil-ity of the process of completing the wireframe. Completing the topology of extrusions from a known front end cap is straightforward.Figure17shows a draw-ing and the corresponding completed extrusionwireframe.Figure17:ExtrusionKnowing that the object is a normalon simplifies recon-struction of the wireframe,since when hypothesised edges are projected along axes,there is usually only one possibil-ity from any particular incomplete vertex.Figure18shows a drawing of a normalon and the corresponding completed wireframe.Similarly,if the object is trihedral,there canbeFigure18:Normalon[Yan85]at most one new edge from each incomplete vertex,simplify-ing reconstruction of the correct wireframe.Figure19shows a drawing of a trihedral object and the corresponding com-pletedwireframe.Figure19:Trihedral Object[Yan85] However,in the general case,where the object is neither a normalon nor trihedral,there is the significant difference that hypothesised edges may be projected in any direction paral-lel to an existing edge.Even after eliminating edges which would be visible,there may be several possibilities at any given incomplete vertex.The large number of possible op-tions rapidly becomes confusing and it is easy to choose an incorrect crossing-point at an early stage.Although such er-rors can sometimes be rectified by backtracking,the more common result is a valid but unwanted wireframe.Only very simple drawings can be processed reliably.Figure20shows a general-case object and the corresponding completed wire-frame;this represents the limit of the current state of theart.Figure20:General Case ObjectOne particular problem,a specific consequence of the ap-proach of completing the wireframe before faces,is thatsubmitted to EUROGRAPHICS Workshop on (2004)8P.Varley&R.Martin&H.Suzuki/Can Machines Interpret Line Drawings?there is no assurance that the local environments of either end of a new edge match.It may happen that a sector around a new edge is solid at one end and empty at the other.This is perhaps the single most frequent cause of failure at present, and is especially problematic in that the resulting completed wireframe can appear correct.We aim to investigate faster and more reliable ways of determining the correct hidden topology of an object,starting with approaches aimed at cor-recting this conflicting local environment problem. Adding additional faces to the completed wireframe topology for which the frontal geometry is already known is straightforward.We use repeated applications of Dijkstra’s Algorithm[Dij59]tofind the best loop of unallocated half-edges for each added face,where the merit for a loop of half-edges is based both on the number of half-edges re-quired(the fewer,the better)and their geometry(the closer to coplanar,the better).We have not known this approach to fail when the input is a valid wireframe(which,as noted above,is not always the case).9.Beautification of Solid ModelsAs can be seen from the Figures in the previous Section, even when topologically correct,the solid models produced may have(possibly large)geometric imperfections.They re-quire‘beautification’.More formally,given a topologically-correct object and certain symmetry and regularity hypothe-ses,we wish to translate these hypotheses into constraints, and update the object geometry so that it maximises some merit function based on the quantity and quality of con-straints enforced.In order to make this problem more tractable,we decom-pose it into determination of face normals and determination of face distances from the origin;once faces are known,ver-tex coordinates may be determined by intersection.The ra-tionale for this partitioning[KY01]is that changing face nor-mals can destroy satisfied distance constraints,but changing face distances cannot destroy satisfied normal constraints. However,there are theoretical doubts about this sub-division,related to the resolvable representation prob-lem[Sug99]offinding a‘resolution sequence’in which information can befixed while guaranteeing that no previ-ous information is contradicted.For example,determining face equationsfirst,and calculating vertex coordinates from them,is a satisfactory resolution sequence for many polyhe-dra,including all trihedral polyhedra.Similarly,fixing vertex coordinates and calculating face planes from them is a satis-factory resolution sequence for deltahedra and triangulated mesh models.Sugihara[Sug99]proved that:•all genus0solids have resolution sequences(although if neither trihedral nor deltahedra,finding the resolution se-quence might not be straightforward);•(by counterexample)genus non-zero solids do not neces-sarily have resolution sequences.Thus,there are two resolvable representation issues:•finding a resolution sequence for those solids which have a non-trivial resolution sequence;•producing a consistent geometry for those solids which do not have a resolution sequence.Currently,neither problem has been solved satisfactorily. Thus,although there are objects which have resolution se-quences,but for which determining face normals,and then face distances,andfinally vertex coordinates,is not a satis-factory resolution sequence,the frequency of occurrence of such objects has yet to be determined.If low,the pragmatic advantages of such an approach are perhaps more important than its theoretical inadequacy.Our overall beautification algorithm is[Var03a]:•Make initial estimates of face normals•Use any object classification to restrict face normals •Identify constraints on face normals•Adjust face normals to match constraints •Make initial estimates of face distances •Identify constraints on face distances•Adjust face distances to match constraints •Obtain vertex locations by intersecting planes in threes •Detect vertex/face failures and adjust faces to correct them We use numerical methods for constraint processing,as this seems to be the approach which holds most promise.Al-ternatives,although unfashionable for various reasons,may become more viable as the state of the art develops:see Lip-son et al[LKS03]for a discussion.In addition to the resolvable representation problem,there is a further theoretical doubt about this approach.When at-tempting to satisfy additional constraints,it is necessary to know how many degrees of freedom are left in the system once previous,already-accepted,constraints are enforced. This apparently-simple problem appears to have no fully-reliable solution.One solution proposed by Li[LHS01]per-turbs the variables slightly and detects which constraints have been violated.However,this is slow,and not necessar-ily theoretically sound either(e.g.a constraint relating face distances A and B may allow them to move together,but not independently of one another).Two differing approaches have been tried to the problem offinding whether or not a geometry exists which satis-fies a new constraint while continuing to satisfy previously-accepted constraints.Thefirst encodes constraint satisfaction as an error func-tion(the lower the value,the better-satisfied the con-straint),and face normals and/or face distances as vari-ables,using a downhill optimiser to minimise the error function[CCG99,LMM02,Var03a].Such algorithms use a ‘greedy’approach,in which the constraint with the highest figure of merit is always accepted and enforced,and then for each other constraint,in descending order of merit:if thesubmitted to EUROGRAPHICS Workshop on (2004)。

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.17, No.10, October 2006, pp.2029−2039 DOI: 10.1360/jos172029 Tel/Fax: +86-10-62562563© 2006 by Journal of Softwar e. All rights reserved.∗分布式约束满足问题研究及其进展王秦辉, 陈恩红+, 王煦法(中国科学技术大学计算机科学技术系,安徽合肥 230027)Research and Development of Distributed Constraint Satisfaction ProblemsWANG Qin-Hui, CHEN En-Hong+, WANG Xu-Fa(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China)+ Corresponding author: Phn: +86-551-3602824, Fax: +86-551-3603388, E-mail: cheneh@Wang QH, Chen EH, Wang XF. Research and development of distributed constraint satisfaction problems.Journal of Software, 2006,17(10):2029−2039. /1000-9825/17/2029.htmAbstract: With the rapid development and wide application of the Internet technology, many problems ofArtificial Intelligence, for example scheduling, planning, resource allocation etc., are formally distributed now,which turn into a kind of multi-agent system problems. Accordingly, the standard constraint satisfaction problemsturn into distributed constraint satisfaction problems, which become the general architecture for resolvingmulti-agent system. This paper first briefly introduces the basic concepts of distributed CSPs, and then summarizesthe basic and the improved algorithms. Their efficiency and performance are analyzed and the typical applicationsof distributed CSPs in recent years are discussed. Finally, this paper presents the extensions of the basicformalization and the research trends in this area. Recent related work indicates that the future work will focus onthe theoretical research to present the solid theoretical foundation for the practical problems.Key words: constraint satisfaction; distributed AI; multi-agent system; search; asynchronous摘 要: 近年来,随着网络技术的快速发展和广泛应用,人工智能领域中的诸多问题,如时序安排、计划编制、资源分配等,越来越多地以分布形式出现,从而形成一类多主体系统.相应地,求解该类问题的传统约束满足问题也发展为分布式约束满足问题,分布式约束满足已经成为多主体系统求解的一般框架.首先,简要介绍了分布式约束满足问题的基本概念,总结了该问题的基本算法及其改进算法,并对这些算法的效率和性能进行了比较分析.然后,讨论了近年来分布式约束满足问题的若干典型应用;最后,给出了分布式约束满足问题基本形式的扩展和今后的研究方向.分布式约束满足问题最新研究进展表明:今后的工作将着重于面向现实问题求解的理论研究,为实际应用提供坚实的理论基础.关键词: 约束满足;分布式人工智能;多主体系统;搜索;异步中图法分类号: TP301文献标识码: A自1974年Montanari在图像处理中首先提出了约束满足问题(constraint satisfaction problems,简称CSPs)[1]∗ Supported by the National Natural Science Foundation of China under Grant No.60573077 (国家自然科学基金); the Program forNew Century Excellent Talents in University of China under Grant No.NCET-05-0549 (新世纪优秀人才支持计划)Received 2006-03-09; Accepted 2006-05-082030 Journal of Software软件学报 V ol.17, No.10, October 2006以来,约束满足作为一种重要的求解方法在人工智能与计算机科学其他领域的很多问题中都得到了广泛的应用[2],从n皇后、图染色等经典问题到时序安排、计划编制、资源分配等大型应用问题,都可以形式化为约束满足问题进行求解.正因为在人工智能领域中的广泛适用,约束满足问题在理论、实验、应用上都得以深入研究,成为人工智能中很成功的问题解决范例之一.其相关成果一直是人工智能权威期刊《Artificial Intelligence》的热点,并有多个专题对此进行讨论;国内也有很多学者致力于约束满足问题的研究,主要的工作有约束程序理论、设计与应用的研究[3,4]、约束归纳逻辑程序设计等方面的研究[5,6],以及约束满足问题的求解研究[7−9]等等.约束满足问题是由一系列变量、变量相应的值域以及变量之间的约束关系组成,目标是为这些变量找到一组或多组满足所有约束关系的赋值.回溯搜索以及约束一致性检查两种基本思想和引入它们中的各种启发式方法构成了多种约束满足问题求解算法.随着硬件和网络技术的发展,分布式计算环境快速、广泛地在各个领域中得到应用,很多人工智能问题也越来越多地处于分布式计算环境下,使得分布式人工智能成为一个十分重要的研究领域,特别是关系到人工自治Agent间需要相互协调影响的分布式问题.如在多智能体系统(multi-agent system,简称MAS)中,处于同一环境下的Agent间通常存在着某种约束,此时,为各个Agent寻找一组满足它们之间约束的动作组合的分布式人工智能应用问题都可以看作是分布式约束满足问题(distributed CSPs).分布式约束满足问题是变量以及变量间的约束都分布在不同自治Agent中的约束满足问题,每个Agent控制一个或多个变量,并试图决定这些变量的值,一般在Agent内和Agent间都存在约束关系,对变量的赋值要满足所有这些约束.正因为不同的变量和约束是由不同的Agent控制,因此,在这种情形下,将所有Agent控制的变量及相关的约束等信息集中到一个Agent,再用传统的集中式约束满足算法进行求解往往是不充分或者是不可能的,有如下几点原因[10]:(1) 生成集中控制会带来额外开销.如类似于传感网络的约束满足问题很可能自然地分布在由一些同等Agent构成的集合中.这种情况下,对问题进行集中控制就需要增加不出现在原有结构中的额外元素.(2) 信息传递的开销.在很多情况下,约束由复杂的决策过程产生,这些过程是内在于Agent并且不可能被集中控制的.集中式算法需要获得这些约束关系就要承担信息传递的开销.(3) 隐私和安全的保证.在电子商务等情况中,常出现Agent之间的约束是不能泄露给竞争者甚至也不能泄露给集中控制的战略信息的情况.此时,隐私只能在分布式方法中得到很好的保护.(4) 面对失败的鲁棒性.集中控制求解时的失败可能是致命的;而在分布式方法中,一个Agent的失败并不是致命的,其他Agent可以在忽略已失败Agent的情况下找到问题的解.比如在传感网络和基于网络的应用中,当约束求解过程正在进行而参与者可能离开时,都会产生这些问题.从上述原因可以看出:此类分布式环境中的问题需要更有效的解决方法.随着人工智能领域协作式分布问题研究的深入,Yokoo等人在文献[11]中提出了分布式约束满足问题的框架和相应算法.作为一种新的技术,它特别适用于表示及求解规模大、难度高的组合问题.所以,分布式约束满足问题成为人工智能领域的一个研究热点.本文在文献[12]对分布式约束满足问题综述的基础上,不仅介绍了分布式约束满足的问题形式和一系列求解算法,还介绍了近年来在分布式约束满足问题基本形式上的扩展和多主体系统的应用.本文第1节介绍分布式约束满足问题的定义.第2节详述一系列求解分布式约束满足问题的算法,比如异步回溯、异步Weak-commitment搜索、分布式逃逸算法等.第3节介绍相应的应用.最后总结该问题上的一些扩展和类似的工作,如开放式、分布式局部约束满足、隐私安全性等.1 分布式约束满足1.1 约束满足问题约束满足问题是在一定的值域范围内为所有变量寻找满足它们彼此间约束关系的赋值的问题,由变量、变量的值域和变量之间的约束组成.定义1(约束满足问题). 约束满足问题可以形式化为一个约束网[13],由变量的集合、每个变量的值域的集合以及变量间的约束关系的集合来定义,表示为三元组(V,D,C),其中:王秦辉等:分布式约束满足问题研究及其进展2031V是变量的集合{v1,…,v n};D是所有变量的值域的集合,D={D1,…,D n}, D i是变量v i的所有可能取值的有限域;C是变量之间的约束关系的集合C={C1,…,C m},其中每个约束包含一个V的子集{v i,…,v j}和一个约束关系R⊆D i×…×D j.约束满足方法是一种有效的问题求解方法,它为每个变量在其值域中寻找一个赋值,使得所有约束被满足.定义2(约束满足问题的解). 约束满足问题的解是分配给问题中所有变量的一组不违反任何约束的赋值.也即一组对所有变量的赋值S(v1,…,v n)={d1∈D1,…,d n∈D n},∀C r∈C都有S(v ri,…,v rj)={d ri,…,d rj}∈R r.例如,n皇后问题就是典型的约束满足问题.该问题描述为要在n×n的棋盘上摆放n个皇后,使得每一行、每一列和每条对角线上只能有一个皇后存在.图1是4皇后问题的示例以及相应的约束满足问题.(a) (b) (d)Fig.1 4 queens constraint satisfaction problem图1 4皇后及相应的约束满足问题图1(a)表示在4×4的棋盘上放置4个皇后Q1~Q4,即为变量集合;图1(b)表示任意行、列、对角线上不能同时有两个皇后,即为约束关系;图1(c)是相对应的约束满足关系网;图1(d)是该问题的一个解.1.2 分布式约束满足问题分布式约束满足问题是变量和约束都分布在不同自治Agent中的约束满足问题.在约束满足问题定义的基础上,可如下定义分布式约束满足问题:定义3(分布式约束满足问题). n个Agent表示为A1,A2,…,A n,m个变量为v1,v2,…,v m,m个变量的值域为D1, D2,…,D m,变量间的约束仍用C表示;每个Agent有一个或多个变量,每个变量v j属于一个A i,表示为belongs(v j, A i);变量间的约束关系分布在Agent内或Agent之间,当A l知道约束关系C k时,表示为Known(C k,A l).分布在Agent内的约束称为局部约束,而Agent间的约束称为全局约束,局部约束可以通过Agent的计算来处理,全局约束不仅需要Agent的计算,更需要Agent间的通信来处理,因此需要如下的通信模式假设: 假设1. Agent间的通信通过传递消息完成,当且仅当一个Agent知道对方地址时才能够传递消息给其他Agent.假设2. 传递消息的延时是随机但有限的,任何一对Agent间消息接收的顺序与消息发送的顺序是一致的.假设3. 每个Agent只知道整个问题的部分信息.分布式约束满足中的Agent与多智能体系统(MAS)中的Agent有着细小的差别[14],分布式约束满足中的Agent是遵从协作机制来执行决策行为的计算实体;MAS中的Agent自治地决定是否遵从特定的协作机制,并能以结构化的语义消息交换形式与其他Agent进行通信.在将MAS形式化为分布式约束满足问题进行求解时,并不考虑这些区别.每一个Agent负责一些变量并决定它们的值,因为还存在着Agent间的内在约束,所以,赋值必须满足这些约束.分布式约束满足问题的解的形式化定义为:定义4(分布式约束满足问题的解). 当且仅当满足下述条件时,分布式约束满足问题找到了解:∀A i,∀v j存在关系belongs(v j,A i),当v j的赋值是d j∈D j时,∀C k,∀A l,Known(C k,A l)都有C k被满足.也即此时对问题中所有变量的赋值满足Agent间及Agent内的所有约束.2032 Journal of Software 软件学报 V ol.17, No.10, October 2006图2是一个分布式约束满足问题的示例.该问题为分布式图染色问题,从黑、白、灰这3种颜色中选一种分配给Agent 中的节点变量,使得互相连接的节点颜色不同.图中每个Agent 都各有3个变量,变量之间的边就表示彼此间存在着约束关系,该问题不仅Agent 内而且Agent 间都存在着约束关系.(a) (b) (c)Fig.2 Example of distributed constraint satisfaction problem图2 分布式约束满足问题示例图2(a)表示该问题的约束关系网;图2(b)为随机分配着色的初始状态;图2(c)是该问题的一个解.1.3 分布式约束满足与并行/分布式计算的区别分布式约束满足问题看起来与求解约束满足问题的并行/分布式方法[15,16]虽然很相似,但它们从根本上是不同的.并行/分布式方法应用到约束满足问题求解中的目的是为了提高问题的求解效率,针对不同的约束满足问题可以选择任何一种合适的并行/分布式计算机体系结构将问题分而治之,取得较高的求解效率.而在分布式约束满足中,问题的变量和约束等相关信息从问题给定时就既定地分布于各个自治Agent 中,所以,研究的出发点是如何在这种固有的情形下有效地获得问题的解.比如一个大规模的n 皇后问题,可以利用分布式并行计算获得更快的求解速度.而对应到分布式的n 皇后问题,则是很多个不同的Agent 拥有数量不同的皇后,通过自我决策和Agent 间的通信协作来共同达到问题的解.2 求解分布式约束满足问题的算法在分布式约束满足问题提出的同时,Yokoo 就在文献[11]中提出了异步回溯算法.近些年来,其他的分布式约束满足求解算法也得到了进一步的研究,特别是异步Weak-commitment 搜索[17,18]和分布式逃逸算法[19]等.这些算法基本上是由约束满足问题的求解算法而来,是这些传统算法的分布式扩展.但是,因为分布式约束满足问题中Agent 之间也存在着约束关系,所以,Agent 间需要通信是与传统算法的最大区别.分布式约束满足算法有两种最基本的消息需要通信,分别是ok ?和nogood [11].定义5(ok ?消息). ok ?是指Agent 将当前的赋值信息传递给相邻Agent 的消息.定义6(nogood 消息). nogood 是用来传递约束是否发生冲突而产生新约束的消息.在文献[12]中,对各种算法的描述都做了如下假设:(1) 每个Agent 只控制一个变量;(2) 所有的约束都是二元的;(3) 每个Agent 知道所有和自己变量相关的约束.因此,可以不加区分地使用相同标识v i 表示一个Agent 及其变量,用约束网中的有向边表示约束关系,该有向边由发送消息Agent 指向接收消息Agent.对假设2和假设3都可以自然地扩展到一般情形.下面分别介绍基于回溯的异步回溯算法、基于优化迭代的分布式逃逸算法和基于混合算法的异步Weak-commitment 算法.2.1 异步回溯(AB :Asynchronous backtracking )异步回溯算法是由求解约束满足问题的回溯算法而来.所不同的是,异步回溯算法是分布式的、异步的.在异步回溯算法中,每个Agent 都有一个优先顺序,该优先顺序是预先定义好的,一般由Agent 标识的字母顺序来王秦辉等:分布式约束满足问题研究及其进展2033决定,比如,按降序或升序来决定Agent的优先序的高低.在该算法中,每个Agent除了要发送接受ok?和nogood 消息以外,还要维护一个agent_view,这是用来记录其他Agent的当前赋值的.当一个Agent接收到ok?消息时,则检查其赋值与优先顺序高的Agent的当前赋值是否满足约束关系,如果不满足约束关系产生冲突而不一致就改变自己的赋值;如果该Agent值域中没有能与高优先序Agent的赋值相一致的值,就产生一个新的约束关系(也就是nogood),并且将nogood传递给高优先序Agent,这样,高优先序Agent就可以改变自己的赋值.必须注意到:如果Agent不断地改变它们的赋值而不能达到一个稳定状态,那么它们就处于一种无限处理循环,当一个Agent的赋值导致其他Agent改变赋值而最终影响到自己时就可能产生这种无限循环.为了避免这种情况的发生,在算法中,按照标识的字母序为每个Agent定义了优先顺序,ok?只能从高优先序Agent发送给低优先序Agent.当产生nogood时,也是nogood中的优先序最低的Agent接收到nogood消息.另外,每个Agent的行动都是同时异步发生的,而且Agent间的通信是通过消息传递来进行的,所以,agent_view中可能包含有已经无用的信息.因此,每个Agent都需要产生新的nogood进行通信,新nogood的接收方也必须检查在自己的agent_view的基础上与此nogood是否有冲突.因为算法中最高优先序的Agent不会陷入无限处理循环中,文献[18]用归纳法证明了该算法是具备完全性的,也即:如果问题有解存在,那么一定能找到这个解;如果没有解存在,那么算法也会终止,不会陷入无限循环.近年来,有很多工作都对异步回溯算法进行了改进.在对算法进行扩展时,文献[20]采用了Agent的动态重排序;文献[21]引入了一致性维护;文献[22]提出了不存储nogood消息的分布式回溯算法.这些算法与基本的异步回溯算法相比只是存储nogood消息的方式不同,它们都需要在未相连的Agent之间添加通信连接来检测已经无用的消息.而文献[23]中提出了一种新的异步回溯算法来避免在初始未相连的Agent之间动态地增添新的约束,这样就可以避免将一些信息传递给不需要知道的Agent,从而提高效率.文献[24]从另一个角度提出了如何利用值聚集来减少信息阻塞以及如何利用弧一致维护来提高异步分布式下问题求解的有效性.2.2 异步Weak-Commitment搜索(AWS:Asynchronous weak-commitment search)异步回溯算法的局限在于Agent的优先顺序是预先定义好的,是静态的.如果高优先序Agent的赋值选择得不好,那么,低优先序Agent就要进行穷尽查找来修正不利的赋值.异步Weak-commitment搜索算法[17,18]的两个基本思想是:为了减少不利赋值的风险而引入了最小冲突启发;更进一步地,Agent的优先级顺序是可以动态改变的,这样,不利赋值不需要穷尽搜索就能够得到更正.最小冲突启发是指Agent选择值域中那些与其他Agent的赋值产生最少冲突的值作为自己的赋值.而为了使Agent的优先级顺序能够动态改变,特别地为Agent引入了优先值,优先值是非负整数,优先值大的Agent具有较高的优先顺序,优先值相等的Agent的优先顺序由它们所标识的字母序来决定.初始时,Agent的优先值均为0,当Agent的赋值与约束发生冲突而不一致时,该Agent的优先值就变为相邻Agent中的最大优先值再加1.与异步回溯算法相比,异步Weak-commitment搜索算法的不同在于:(1) 异步回溯中每个Agent只将变量赋值发送给约束相关的低优先级Agent;而异步Weak-commitment搜索中每个Agent将变量赋值发送给约束相关的所有Agent,无论优先级的高低;(2)ok?消息不仅用来传递Agent的当前赋值,还用来传递Agent的优先值;(3) 如果当前的赋值与agent_view不一致,则Agent用最小冲突启发来改变赋值;(4) 如果Agent不能找到与自己的agent_view一致的赋值,就发送nogood消息给其他Agent,同时改变自己的优先值.如果Agent不能生成新的nogood,那么就不改变自己的优先值,并等待下一条消息.第4步的过程是保证算法的完全性所必需的.因为优先值的改变只有在新的nogood产生时才发生,而可能的nogood的数量是有限的,优先值不可能无限地改变,所以到了某个时间之后,优先值就稳定下来,此后,过程就与异步回溯算法一样,故而算法是完全的.为了保证算法的完全性,Agent要记录所有目前已知的nogood,实际操作时,可以限制记录nogood的数目,比如每个Agent只记录固定数目的最近发生的nogood消息.正如前面所提到的假设,这些算法中的Agent都只含有一个变量,对于解决Agent含有多个变量的问题,无论是采用先让Agent找到自己局部问题的所有解后再将问题重新形式化为分布式约束满足问题来求解,还是让2034 Journal of Software软件学报 V ol.17, No.10, October 2006Agent为每个局部变量生成一个虚拟Agent再来模拟这些Agent的动作来求解,对大规模问题而言,既没有效率也不能扩展.文献[25]对异步Weak-commitment搜索算法进行了扩展,利用变量顺序来解决多个局部变量的问题,称为Multi-AWS.它的特点是Agent按顺序来改变自己变量的值,当某个变量不存在满足所有与高优先序的变量有关的约束时,就增加该变量的优先值.不断反复该过程,当Agent中所有局部变量都与高优先序变量满足约束时,就传递值改变消息给相关的Agent.2.3 分布式逃逸(DB:Distributed breakout)在最小冲突回溯等约束满足算法中的爬山(hill-climbing)搜索策略,有时会使求解过程陷入局部最小(local-minima)状态.local-minima状态就是一些约束没有被满足从而出现了冲突,但是这些冲突的数目不能通过单独改变任何一个变量的值来减少.文献[26]中提出的逃逸算法是一种跳出local-minima状态的方法,算法中为每个约束定义了权值,所有冲突约束的权值总和作为一个评估值.当陷入local-minima状态时,逃逸算法增加当前状态中冲突约束的权值,使得当前状态的评估值高于其他邻接的状态,从而跳出local-minima状态,开始新的搜索.文献[19]在此基础上通过以下两个步骤来实现分布式逃逸:(1) 始终保证评估值是逐步提高的:相邻的Agent对可能会提高的评估值进行交流,只有能够最大提高评估值的Agent才有权改变自己的值.如果两个Agent不相邻,那么它们有可能同时改变自己的值;(2) 与检测整个Agent是否陷入local-minima不同的是,每个Agent检测其是否处于quasi-local-minima状态,这是比local-minima要弱一些的条件,并且能够通过局部通信而检测到.定义7(Agent A i处于quasi-local-minimum状态). A i的赋值使部分约束产生冲突,并且A i和所有A i邻居的可能提高值均为0.在分布式逃逸算法中,相邻的Agent之间有两种消息的通信:ok?和improve. improve消息用来对可能提高的评估值进行通信,Agent在整个过程中处于wait_ok?和wait_improve两种交替状态.分布式逃逸算法有可能陷入无限循环当中,因而不能保证算法的完全性.文献[27]在对分布式逃逸算法进行扩展时,不仅提出了解决Agent有多个局部变量的Multi-DB算法,还对此算法引入了两种随机方式.一种是利用了随机跳出技术的Multi-DB+算法,另一种是在Multi-DB+中又引入随机行走的Multi-DB++算法.这些算法比其他异步方法有更好的扩展性,但有时也会有更差的性能.2.4 几种算法的比较上面介绍了几种求解分布式约束满足问题的基本算法,这些算法有各自的特点和适用性,也各有优点和局限性,表1是就上述算法在完全性及解决多局部变量方面的一个定性比较.Table 1Comparison of algorithms for solving distributed CSPs表1几种基本分布式约束满足问题求解算法的定性比较Algorithm AB AWS Multi-AWS DB Multi-DBNo NoCompleteness Yes Yes YesMulti local variables No No Yes No Yes文献[12]对基本的异步回溯(AB)、异步Weak-commitment(AWS)和分布式逃逸(DB)算法进行了性能比较.通过离散的事件模拟来评估算法的效率,其中每个Agent维护自己的模拟时钟,只要Agent执行一个计算周期,其时间就增加一个模拟时间单元.一个计算周期包括读取所有消息、执行局部计算和发送消息.假设一个消息在时间t发布,则对接收者来说,在时间t+1时可用.最后,通过解决问题所需的计算周期数量来分析算法的性能.表2是用分布式图染色问题来评测的结果,其中:Agent(变量)的数目n=60,90和120;约束的数量为m=n×2,可能的颜色数目为3.总共生成10个不同的问题,对每个问题执行10次不同的初始赋值,并且限制周期最大为1000,超过后就终止算法.表中列出了算法求解所需的平均周期和求解成功的比例.明显地,AWS算法要优于AB算法,因为在AWS算法中,不需要执行穷尽查找就能修正错误的赋值.在表3和表4比较AWS与DB算法时,Agent(变量)的数目为n=90,120和150,约束的数量分别为m=n×2王秦辉等:分布式约束满足问题研究及其进展2035和m=n×2.7两种情况,可能的颜色数仍然为3.当m=n×2时,可认为Agent间的约束是比较稀疏的;而当m=n×2.7时,则被认为是能够产生阶段跳跃的临界状态[28].Table 2 Comparison between AB and AWS表2算法AB和AWS的比较nAlgorithm60 90 120Ratio (%) 13 0 0ABCycles 917.4 －－Ratio (%) 100 100 100AWSCycles 59.4 70.1 106.4Table 3Comparison between DB and AWS (m=n×2)表3算法DB和AWS的比较(m=n×2)nAlgorithm90 120 150Ratio (%) 100 100 100DBCycles 150.8 210.1 278.8Ratio (%) 100 100 100AWSCycles 70.1 106.4 159.2Table 4Comparison between DB and AWS (m=n×2.7)表4算法DB和AWS的比较(m=n×2.7)nAlgorithm90 120 150Ratio (%) 100 100 100DBCycles 517.1 866.4 1175.5Ratio (%) 97 65 29AWSCycles 1869.6 6428.4 8249.5从表3和表4中可以看出:当问题为临界困难时,DB算法要优于AWS算法.而对于一般情形,AWS算法要优于DB算法.因为在DB算法中,每个模式(wait_ok?或者wait_improve)都需要一个周期,所以每个Agent在两个周期内至多只能改变一次赋值;而在AWS算法中,每个Agent在每个周期内都可以改变赋值.如前所述,近年来的很多工作都对这些基本算法进行了改进或者扩展,在性能和效率方面也有各自的特点.文献[20]中的实验表明:对Agent进行动态重排序的ABTR(ABT with asynchronous reordering)算法的平均性能要优于AB算法,说明额外增加动态重排序的启发式消息实际上是可以提高算法效率的.文献[24]通过实验表明:采用值聚集的AAS(asynchronous aggregation search)算法的效果要稍好一些.虽然在查找第一个解时,不利用值聚集的效果会更好,但是如果解不存在,那么AAS的性能总是要优于不采用值聚集的算法,因为此时需要扩展到整个搜索空间,AAS可以减少消息序列,也就是减少存储nogoods消息的数目.更进一步地,使用了bound- consistency一致维护技术的MHDC(maintaining hierarchical distributed consistency)算法在实验中的整体性能要比AAS有很大的提高.通过图染色实验,文献[25]比较了算法Multi-AWS,AWS-AP(Agent priority)和Single-AWS,对于Agent有多个变量的情况,Multi-AWS算法在执行周期以及一致性检查数目上都要优于其他两种算法,而且随着Agent或变量的增多,其性能就越优于AWS-AP算法和Single-AWS算法.这是因为在解决Agent有多个变量的问题时,AWS-AP算法和Single-AWS算法需要增加额外的虚拟Agents来将多局部变量分布化,这样就增加了Agents 间的通信,从而使性能降低.文献[27]首先比较了Multi-DB和Multi-AWS算法.Multi-DB算法随着变量数目的增多,效率会越来越优于Multi-AWS算法,在很多情形下会有至少1个数量级的提高,但是成功率却较低.原因是由于Multi-DB算法在查找过程中固有的确定性使算法缺少了随机性.对于实验中Multi-DB++算法的效率优于Multi-DB算法,可以得出结论:多Agent搜索进程中的停滞可以通过添加随机行走来避免.。

CS188Introduction to Artificial IntelligenceSpring2019Note5 These lecture notes are heavily based on notes originally written by Nikhil Sharma.Constraint Satisfaction ProblemsIn the previous note,we learned how tofind optimal solutions to search problems,a type of planning problem.Now,we’ll learn about solving a related class of problems,constraint satisfaction problems (CSPs).Unlike search problems,CSPs are a type of identification problem,problems in which we must simply identify whether a state is a goal state or not,with no regard to how we arrive at that goal.CSPs are defined by three factors:1.Variables-CSPs possess a set of N variables X1,...,X N that can each take on a single value from somedefined set of values.2.Domain-A set{x1,...,x d}representing all possible values that a CSP variable can take on.3.Constraints-Constraints define restrictions on the values of variables,potentially with regard to othervariables.Consider the N-queens identification problem:given an N×N chessboard,can wefind a configuration in which to place N queens on the board such that no two queens attack each another?We can formulate this problem as a CSP as follows:1.Variables-X i j,with0≤i,j<N.Each X i j represents a grid position on our N×N chessboard,with iand j specifying the row and column number respectively.2.Domain-{0,1}.Each X i j can take on either the value0or1,a boolean value representing theexistence of a queen at position(i,j)on the board.3.Constraints-•∀i,j,k(X i j,X ik)∈{(0,0),(0,1),(1,0)}.This constraint states that if two variables have the samevalue for i,only one of them can take on a value of1.This effectively encapsulates the conditionthat no two queens can be in the same row.•∀i,j,k(X i j,X k j)∈{(0,0),(0,1),(1,0)}.Almost identically to the previous constraint,this con-straint states that if two variables have the same value for j,only one of them can take on a valueof1,encapsulating the condition that no two queens can be in the same column.•∀i,j,k(X i j,X i+k,j+k)∈{(0,0),(0,1),(1,0)}.With similar reasoning as above,we can see thatthis constraint and the next represent the conditions that no two queens can be in the same majoror minor diagonals,respectively.•∀i,j,k(X i j,X i+k,j−k)∈{(0,0),(0,1),(1,0)}.X i j=N.This constraint states that we must have exactly N grid positions marked with a1,•∑i,jand all others marked with a0,capturing the requirement that there are exactly N queens on theboard.Constraint satisfaction problems are NP-hard,which loosely means that there exists no known algorithm for finding solutions to them in polynomial time.Given a problem with N variables with domain of size O(d)for each variable,there are O(d N)possible assignments,exponential in the number of variables.We can often get around this caveat by formulating CSPs as search problems,defining states as partial assignments (variable assignments to CSPs where some variables have been assigned values while others have not). Correspondingly,the successor function for a CSP state outputs all states with one new variable assigned, and the goal test verifies all variables are assigned and all constraints are satisfied in the state it’s testing. Constraint satisfaction problems tend to have significantly more structure than traditional search problems, and we can exploit this structure by combining the above formulation with appropriate heuristics to hone in on solutions in a feasible amount of time.Constraint GraphsLet’s introduce a second CSP example:map coloring.Map coloring solves the problem where we’re given a set of colors and must color a map such that no two adjacent states or regions have the same color.Constraint satisfaction problems are often represented as constraint graphs,where nodes represent variables and edges represent constraints between them.There are many different types of constraints,and each is handled slightly differently:•Unary Constraints-Unary constraints involve a single variable in the CSP.They are not represented in constraint graphs,instead simply being used to prune the domain of the variable they constrain when necessary.•Binary Constraints-Binary constraints involve two variables.They’re represented in constraint graphs as traditional graph edges.•Higher-order Constraints-Constraints involving three or more variables can also be represented with edges in a CSP graph,they just look slightly unconventional.Consider map coloring the map of Australia:The constraints in this problem are simply that no two adjacent states can be the same color.As a result,by drawing an edge between every pair of states that are adjacent to one another,we can generate the constraint graph for the map coloring of Australia as follows:The value of constraint graphs is that we can use them to extract valuable information about the structure of the CSPs we are solving.By analyzing the graph of a CSP,we can determine things about it like whether it’s sparsely or densely connected/constrained and whether or not it’s tree-structured.We’ll cover this more in depth as we discuss solving constraint satisfaction problems in more detail.Solving Constraint Satisfaction ProblemsConstraint satisfaction problems are traditionally solved using a search algorithm known as backtracking search.Backtracking search is an optimization on depthfirst search used specifically for the problem of constraint satisfaction,with improvements coming from two main principles:1.Fix an ordering for variables,and select values for variables in this order.Because assignments arecommutative(e.g.assigning WA=Red,NT=Green is identical to NT=Green,WA=Red),this is valid.2.When selecting values for a variable,only select values that don’t conflict with any previously as-signed values.If no such values exist,backtrack and return to the previous variable,changing its value.The pseudocode for how recursive backtracking works is presented below:For a visualization of how this process works,consider the partial search trees for both depthfirst search and backtracking search in map coloring:Note how DFS regretfully colors everything red before ever realizing the need for change,and even then doesn’t move too far in the right direction towards a solution.On the other hand,backtracking search only assigns a value to a variable if that value violates no constraints,leading to a significantly less backtracking. Though backtracking search is a vast improvement over the brute-forcing of depthfirst search,we can get more gains in speed still with further improvements throughfiltering,variable/value ordering,and structural explotation.FilteringThefirst improvement to CSP performance we’ll consider isfiltering,which checks if we can prune the domains of unassigned variables ahead of time by removing values we know will result in backtracking.A naïve method forfiltering is forward checking,which whenever a value is assigned to a variable X i, prunes the domains of unassigned variables that share a constraint with X i that would violate the constraint if assigned.Whenever a new variable is assigned,we can run forward checking and prune the domains of unassigned variables adjacent to the newly assigned variable in the constraint graph.Consider our map coloring example,with unassigned variables and their potential values:Note how as we assign WA=red and then Q=green,the size of the domains for NT,NSW,and SA(states adjacent to WA,Q,or both)decrease in size as values are eliminated.The idea of forward checking can be generalized into the principle of arc consistency.For arc consistency,we interpret each undirected edge of the constraint graph for a CSP as two directed edges pointing in opposite directions.Each of these directed edges is called an arc.The arc consistency algorithm works as follows:•Begin by storing all arcs in the constraint graph for the CSP in a queue Q.•Iteratively remove arcs from Q and enforce the condition that in each removed arc X i−→X j,for every remaining value v for the tail variable X i,there is at least one remaining value w for the head variable X j such that X i=v,X j=w does not violate any constraints.If some value v for X i would not work with any of the remaining values for X j,we remove v from the set of possible values for X i.•If at least one value is removed for X i when enforcing arc consistency for an arc X i−→X j,add arcs of the form X k−→X i to Q,for all unassigned variables X k.If an arc X k−→X i is already in Q during this step,it doesn’t need to be added again.•Continue until Q is empty,or the domain of some variable is empty and triggers a backtrack.The arc consistency algorithm is typically not the most intuitive,so let’s walk through a quick example with map coloring:We begin by adding all arcs between unassigned variables sharing a constraint to a queue Q,which gives us Q=[SA→V,V→SA,SA→NSW,NSW→SA,SA→NT,NT→SA,V→NSW,NSW→V]For ourfirst arc,SA→V,we see that for every value in the domain of SA,{blue},there is at least one value in the domain of V,{red,green,blue},that violates no constraints,and so no values need to be pruned from SA’s domain.However,for our next arc V→SA,if we set V=blue we see that SA will have no remaining values that violate no constraints,and so we prune blue from V’s domain.Because we pruned a value from the domain of V,we need to enqueue all arcs with V at the head-SA→V, NSW→V.Since NSW→V is already in Q,we only need to add SA→V,leaving us with our updated queueQ=[SA→NSW,NSW→SA,SA→NT,NT→SA,V→NSW,NSW→V,SA→V]We can continue this process until we eventually remove the arc SA→NT from Q.Enforcing arc consis-tency on this arc removes blue from SA’s domain,leaving it empty and triggering a backtrack.Note that the arc NSW→SA appears before SA→NT in Q and that enforcing consistency on this arc removes blue from the domain of NSW.Arc consistency is typically implemented with the AC-3algorithm(Arc Consistency Algorithm#3),for which the pseudocode is as follows:The AC-3algorithm has a worst case time complexity of O(ed3),where e is the number of arcs(directed edges)and d is the size of the largest domain.Overall,arc consistency is more holistic of a domain pruning technique than forward checking and leads to fewer backtracks,but requires running significantly more computation in order to enforce.Accordingly,it’s important to take into account this tradeoff when deciding whichfiltering technique to implement for the CSP you’re attempting to solve.As an interesting parting note about consistency,arc consistency is a subset of a more generalized notion of consistency known as k-consistency,which when enforced guarantees that for any set of k nodes in the CSP,a consistent assignment to any subset of k−1nodes guarantees that the k th node will have at least one consistent value.This idea can be further extended through the idea of strong k-consistency.A graph that is strong k-consistent possesses the property that any subset of k nodes is not only k-consistent but also k−1,k−2,...,1consistent as well.Not surprisingly,imposing a higher degree of consistency on a CSP is more expensive to compute.Under this generalized definition for consistency,we can see that arc consistency is equivalent to2-consistency.OrderingWe’ve delineated that when solving a CSP,wefix some ordering for both the variables and values involved. In practice,it’s often much more effective to compute the next variable and corresponding value"on thefly" with two broad principles,minimum remaining values and least constraining value:•Minimum Remaining Values(MRV)-When selecting which variable to assign next,using an MRV policy chooses whichever unassigned variable has the fewest valid remaining values(the most con-strained variable).This is intuitive in the sense that the most constrained variable is most likely to run out of possible values and result in backtracking if left unassigned,and so it’s best to assign a value to it sooner than later.•Least Constraining Value(LCV)-Similarly,when selecting which value to assign next,a good policy to implement is to select the value that prunes the fewest values from the domains of the remain-ing unassigned values.Notably,this requires additional computation(e.g.rerunning arc consis-tency/forward checking or otherfiltering methods for each value tofind the LCV),but can still yieldspeed gains depending on usage.StructureAfinal class of improvements to solving constraint satisfaction problems are those that exploit their struc-ture.In particular,if we’re trying to solve a tree-structured CSP(one that has no loops in its constraint graph),we can reduce the runtime forfinding a solution from O(d N)all the way to O(nd2),linear in the number of variables.This can be done with the tree-structured CSP algorithm,outlined below:•First,pick an arbitrary node in the constraint graph for the CSP to serve as the root of the tree(it doesn’t matter which one because basic graph theory tells us any node of a tree can serve as a root).•Convert all undirected edges in the tree to directed edges that point away from the root.Then linearize (or topologically sort)the resulting directed acyclic graph.In simple terms,this just means order the nodes of the graph such that all edges point rightwards.Noting that we select node A to be our root and direct all edges to point away from A,this process results in the following conversion for the CSP presented below:•Perform a backwards pass of arc consistency.Iterating from i=n down to i=2,enforce arc con-sistency for all arcs Parent(X i)−→X i.For the linearized CSP from above,this domain pruning will eliminate a few values,leaving us with the following:•Finally,perform a forward assignment.Starting from X1and going to X n,assign each X i a value consistent with that of its parent.Because we’ve enforced arc consistency on all of these arcs,no matter what value we select for any node,we know that its children will each all have at least one consistent value.Hence,this iterative assignment guarantees a correct solution,a fact which can be proven inductively without difficulty.The tree structured algorithm can be extended to CSPs that are reasonably close to being tree-structured with cutset conditioning.Cutset conditioning involvesfirstfinding the smallest subset of variables in a constraint graph such that their removal results in a tree(such a subset is known as a cutset for the graph). For example,in our map coloring example,South Australia(SA)is the smallest possible cutset:Once the smallest cutset is found,we assign all variables in it and prune the domains of all neighboring nodes.What’s left is a tree-structured CSP,upon which we can solve with the tree-structured CSP algorithm from above!The initial assignment to a cutset of size c may leave the resulting tree-structured CSP(s)with no valid solution after pruning,so we may still need to backrack up to d c times.Since removal of the cutset leaves us with a tree-structured CSP with(n−c)variables,we know this can be solved(or determined that no solution exists)in O((n−c)d2).Hence,the runtime of cutset conditioning on a general CSP is O(d c(n−c)d2),very good for small c.Local SearchAs afinal topic of interest,backtracking search is not the only algorithm that exists for solving constraint satisfaction problems.Another widely used algorithm is local search,for which the idea is childishly simple but remarkably useful.Local search works by iterative improvement-start with some random assignment to values then iteratively select a random conflicted variable and reassign its value to the one that violates the fewest constraints until no more constraint violations exist(a policy known as the min-conflicts heuristic). Under such a policy,constraint satisfaction problems like N-queens becomes both very time efficient and space efficient to solve.For example,in following example with4queens,we arrive at a solution after only2iterations:for N-queens with arbitrarily large N,but also for any randomly generated CSP!However,despite theseadvantages,local search is both incomplete and suboptimal and so won’t necessarily converge to an optimal solution.Additionally,there is a critical ratio around which using local search becomes extremely expensive:SummaryIt’s important to remember that constraint satisfaction problems in general do not have an efficient algorithm which solves them in polynomial time with respect to the number of variables involved.However,by using various heuristics,we can oftenfind solutions in an acceptable amount of time:•Filtering-Filtering handles pruning the domains of unassigned variables ahead of time to prevent unnecessary backtracking.The two importantfiltering techniques we’ve covered are forward checking and arc consistency.•Ordering-Ordering handles selection of which variable or value to assign next to make backtracking as unlikely as possible.For variable selection,we learned about a MRV policy and for value selection we learned about a LCV policy.•Structure-If a CSP is tree-structured or close to tree-structured,we can run the tree-structured CSP algorithm on it to derive a solution in linear time.Similarly,if a CSP is close to tree structured,we can use cutset conditioning to transform the CSP into one or more independent tree-structured CSPs and solve each of these separately.加入“知识星球 行业与管理资源”库，每日免费获取报告1、每月分享1000+份最新行业报告（涵盖科技、金融、教育、互联网、房地产、生物制药、医疗健康等最新行业）2、每月分享500+企业咨询管理文件（涵盖国内外著名咨询公司相关管理方案，企业运营制度等）3、每月分享500+科技类论文或者大师课件、笔记。

Temporal Constraint Reasoning With PreferencesLina Khatib Paul Morris Robert Morris1.Kestrel Technologyputational Sciences DivisionNASA Ames Research Center,MS269-2Moffett Field,CA94035Francesca RossiDipartimento di Matematica Pura ed ApplicataUniversita’di PadovaVia Belzoni7,35131Padova,ItalyAbstractA number of reasoning problems involving the ma-nipulation of temporal information can be viewedas implicitly inducing an ordering of decisions in-volving time(associated with durations or order-ings of events)on the basis of preferences.Forexample,a pair of events might be constrained tooccur in a certain order,and,in addition,it mightbe preferable that the delay between them be aslarge,or as small,as possible.This paper exploresproblems in which a set of temporal constraints isspecified,each with preference criteria for mak-ing local decisions about the events involved in theconstraint.A reasoner must infer a complete so-lution to the problem such that,to the extent pos-sible,these local preferences are met in the bestway.Constraint-based temporal reasoning is gener-alized to allow for reasoning about temporal prefer-ences,and the complexity of the resulting formal-ism is examined.While in general such problemsare NP-complete,some restrictions on the shape ofthe preference functions,and on the structure of theset of preference values,can be enforced to achievetractability.In these cases,a generalization of asingle-source shortest path algorithm can be usedto compute a globally preferred solution in polyno-mial time.1Introduction and MotivationSome real world temporal reasoning problems can naturally be viewed as involving preferences associated with decisions such as how long a single activity should last,when it should occur,or how it should be ordered with respect to other ac-tivities.For example,an antenna on an earth orbiting satellite such as Landsat7must be slewed so that it is pointing at a ground station in order for recorded science data to be down-linked to earth.Assume that as part of the daily Landsat7 scheduling activity a window is identified within which a slewing activity to one of the ground stations for one of the antennae can begin,and thus there are choices for as-signing the start time for this activity.Antenna slewing on Landsat7has been shown to cause a vibration to the satellite, which in turn affects the quality of the observation taken by the imaging instrument if the instrument is in use during slew-ing.Consequently,it is preferable for the slewing activity not to overlap any scanning activity,although because the detri-mental effect on image quality occurs only intermittently,this disjointness is best not expressed as a hard constraint.Rather, the constraint is better expressed as follows:if there are any start times within such that no scanning activity occurs during the slewing activity starting at,then is to be pre-ferred.Of course,the cascading effects of the decision to assign on the sequencing of other satellite activities must be taken into account as well.For example,the selection of, rather than some earlier start time within,might result in a smaller overall contact period between the ground station and satellite,which in turn might limit the amount of data that can be downlinked during this period.This may conflict with the preference for maintaining maximal contact times with ground stations.Reasoning simultaneously with hard temporal constraints and preferences,as illustrated in the example just given,is the subject of this paper.The overall objective is to develop a system that will generate solutions to temporal reasoning problems that are globally preferred in the sense that the so-lutions simultaneously meet,to the best extent possible,all the local preference criteria expressed in the problem.In what follows a formalism is described for reasoning about temporal preferences.This formalism is based on a generalization of the Temporal Constraint Satisfaction Prob-lem(TCSP)framework[Dechter et al,1991],with the addi-tion of a mechanism for specifying preferences,based on the semiring-based soft constraint formalism[Bistarelli et.al., 1997].The result is a framework for defining problems in-volving soft temporal constraints.The resulting formulation, called Temporal Constraint Satisfaction Problems with Pref-erences(TCSPPs)is introduced in Section2.A sub-class of TCSPPs in which each constraint involves only a single interval,called Simple Temporal Problems with Preferences (STPPs),is also defined.In Section3,we demonstrate the hardness of solving general TCSPPs and STPPs,and pinpoint one source of the hardness to preference functions whose “better”values may form a non-convex set.Restricting the class of admissible preference functions to those with convex intervals of“better”values is consequently shown to result in a tractable framework for solving STPPs.In section4,an algorithm is introduced,based on a simple generalization ofthe single source shortest path algorithm,forfinding globally best solutions to STPPs with restricted preference functions. In section5,the work presented here is compared to other approaches and results.2Temporal Constraint Problems with PreferencesThe proposed framework is based on a simple merger of two existing formalisms:Temporal Constraint Satisfaction Prob-lems(TCSPs)[Dechter et.al.,1991],and soft constraints based on semirings[Bistarelli et.al.,1997]1.The result of the merger is a class of problems called Temporal Constraint Satisfaction problems with preferences(TCSPPs).In a TC-SPP,a soft temporal constraint is represented by a pair con-sisting of a set of disjoint intervals and a preference function:,where,and is a set of preference values.Examples of preference functions involving time are:min-delay:any function in which smaller distances are preferred,that is,the delay of the second event w.r.t.the first one is minimized.max-delay:assigning higher preference values to larger distances;close to k:assign higher values to distances which are closer to;in this way,we specify that the distance be-tween the two events must be as close as possible to. As with classical TCSPs,the interval component of a soft temporal constraint depicts restrictions either on the start times of events(in which case they are unary),or on the dis-tance between pairs of distinct events(in which case they are binary).For example,a unary constraint over a variable representing an event,restricts the domain of,representing its possible times of occurrence;then the interval constraint is shorthand for.A binary constraint over and,restricts the values of the distance,in which case the constraint can be expressed as.A uni-form,binary representation of all the constraints results from introducing a variable for the beginning of time,and re-casting unary constraints as binary constraints involving the distance.An interesting special case occurs when each constraint of a TCSPP contains a single interval.We call such problems Simple Temporal Problems with Preferences(STPPs),due to the fact that they generalize STPs[Dechter et.al.,1991]. This case is interesting because STPs are polynomially solv-able,while general TCSPs are NP-complete,and the effect of adding preferences to STPs is not immediately obvious.The next section discusses these issues in more depth.A solution to a TCSPP is a complete assignment to all the variables that satisfies the distance constraints.Each solu-tion has a global preference value,obtained by combining thethan false in the order induced by logical or).This semiring thus recasts the classical TCSP framework into a TCSPP. Given a constraint network,it is often useful tofind the corresponding minimal network in which the constraints are as explicit as possible.This task is normally performed by enforcing various levels of local consistency.For TCSPPs,in particular,we can define a notion of path consistency.Given two soft constraints,and,and a semiring, we define:the intersection of two soft constraints and,written,as the soft constraint,where–returns the pairwise intersection of intervalsin and,and–for all;the composition of two soft constraintsand,written,is the soft constraint,where–if and only if there exists a valueand such that,and–,where is the generalization of over sets.A path-induced constraint on variables and is,i.e.,the result of performing on each way of composing paths of size two between and.A constraint is path-consistent if and only if ,i.e.,is at least as strict as.A TCSPP is path-consistent if and only if all its constraints are path-consistent.If the multiplicative operation of the semiring is idem-potent,then it is easy to prove that applying the operationto any constraint of a TCSPP returns an equivalent TCSPP.Moreover,under the same con-dition,applying this operation to a set of constraints returns afinal TCSPP which is always the same independently of the order of application2.Thus any TCSPP can be transformed into an equivalent path-consistent TCSPP by applying the op-eration to all constraints until no change occurs in any constraint.This algorithm,which we call Path,is proven to be polynomial for TCSPs(that is, TCSPPs with the semiring):its complexity is, where is the number of variables and is the range of the constraints[Dechter et.al.,1991].General TCSPPs over the semiring are NP-complete; thus applying Path is insufficient to solve them.On the other hand,with STPPs over the same semiring that coincide with STPs,applying Path is sufficient to solve them.In the re-maining sections,we prove complexity results for both gen-eral TCSPPs and STPPs,and also of some subclasses of prob-lems identified by specific semirings,or preference functions with a certain shape.(a)(b)(c)(d)(e)(f)(g)(h)(i)Figure1:Examples of semi-convex functions(a)-(f)and non-semi-convex functions(g)-(i)consider any given TCSPP.For any pair of variables and ,take each interval for the constraint over and,say ,with associated linear preference function.The in-formation given by each of such intervals can be represented by the following inequalities and equation:, ,and.Then if we choose the fuzzy semiring,the global preference value will satisfy the inequality for each preference function defined in the problem,and the objective is.If instead we choose the semir-ing,where the objective is to minimize the sum of the preference levels,we have and the objective is3.In both cases the resulting set of formulas constitutes a linear programming problem.Linear preference functions are expressive enough for many cases,but there are also several situations in which we need preference functions which are not linear.A typical ex-ample arises when we want to state that the distance between two variables must be as close as possible to a single value. Unless this value is one of the extremes of the interval,the preference function is convex,but not linear.Another case is one in which preferred values are as close as possible to a sin-gle distance value,but in which there are some subintervals where all values have the same preference.In this case,the preference criteria define a step function,which is not convex.A class of functions which includes linear,convex,and also some step functions will be called semi-convex functions. Semi-Convex functions have the property that if one draws a horizontal line anywhere in the Cartesian plane defined by the function,the set of such that is not below the line forms an interval.Figure1shows examples of semi-convex and non-semi-convex functions.More formally,a semi-convex function is one such that,for all,the set such that forms an interval.It is easy to see that semi-convex functions include linear ones, as well as convex and some step functions.For example,the close to k criteria cannot be coded into a linear preference function,but it can be specified by a semi-convex preference function,which could be for andfor.for somefor some and some(since each of and is semi-convex)That closure of the set of semi-convex functions requires a total order and idempotence of the operator is demon-strated by the following example.In what follows we assume monotonicity of the operator.Let a and b be preference values with,,,and. Suppose and are real numbers with.Define for and otherwise.Also definefor and otherwise.Clearly, and are semi-convex functions.Define.Note that for,forand for.Since includes all values except where,is not semi-convex. Now consider the situation where the partial order is not total.Then there are distinct incomparable values a and b that satisfy the condition of the example.We conclude the order must be total.Next consider the case in which idempotence is not satisfied.Then there is a preference value c such that .It follows that.In this case,settingsatisfies the condition of the example.We conclude that idempotence is also required.The results in this section imply that applying the Path al-gorithm to an STPP with only semi-convex preference func-tions,and whose underlying semiring contains a multiplica-tive operation that is idempotent,and whose values are to-tally ordered,will result in a network whose induced soft con-straints also contain semi-convex preference functions.These results will be applied in the next section.5Solving STPPs with Semi-Convex Functions is TractableWe will now prove that STPPs with semi-convex preference functions and an underlying semiring with an idempotent multiplicative operation can be solved tractably.First,we describe a way of transforming an arbitrary STPP with semi-convex preference functions into a STP.Given an STPP and an underlying semiring with the set of prefer-ence values,let and be a soft constraint defined on variables in the STPP,where is semi-convex. Consider the interval defined by(because is semi-convex,this set defines an interval for any choice of).Let this interval define a constraint on the same pair.Performing this transformation on each soft constraint in the original STPP results in an STP,which we refer to as.(Notice that not every choice of will yield an STP that is solvable.)Let be the highest prefer-ence value(in the ordering induced by the semiring)such that has a solution.We will now prove that the solutions of are the optimal solutions of the given STPP. Theorem4Consider any STPP with semi-convex preference functions over a totally-ordered semiring with idempotent.Take as the highest such that has a solution.Then the solutions of are the optimal solutions of the STPP. Proof:First we prove that every solution of is an op-timal solution of STPP.Take any solution of,say. This instantiation,in the original STPP,has value,where is the distance for an as-signment to the variables,,andis the preference function associated with the soft constraint ,with.Now assume for the purpose of contradiction that is not optimal in STPP.That is,there is another instantiation such that.Since, by monotonicity of the,we can have only if each of the is greater than the corresponding. But this means that we can take the smallest such value, call it,and construct.It is easy to see thathas at least one solution,,therefore is not the highest value of,contradicting our assumption.Next we prove that every optimal solution of the STPP is a solution of.Take any optimal for STPP,and assume it is not a solution of.This means that,for some constraint,.Therefore,if we compute in STPP,we have that.Then take any solution of(there are some,by construction of). If we compute in STPP,since=glb(we assume idempotent),we have that,thus was not optimal as initially assumed.This result implies thatfinding an optimal solution of the given STPP with semi-convex preference functions reduces to a two-step search process consisting of iteratively choosing a ,then solving,until is found.Under certain conditions,both phases can be performed in polynomial time, and hence the entire process can be tractable.Thefirst phase can be conducted naively by trying every possible“chop”point and checking whether has a solution.A binary search is also possible.Under certain con-ditions,it is possible to see that the number of chop points is also polynomial,namely:if the semiring has afinite number of elements,which is at most exponential in the number of variables of the given STPP,then a polynomial number of checks is enough using binary search.if the semiring has a countably infinite number of ele-ments,and the preference functions never go to infinity, then let be the highest preference level given by the functions.If the number of values not above is at most exponential in,then again we canfind in a poly-nomial number of steps.The second phase,solving the induced,can be per-formed by transforming the graph associated with this STP into a distance graph,then solving two single-source shortest path problems on the distance graph[Dechter et.al.,1991]. If the problem has a solution,then for each event it is possi-ble to arbitrarily pick a time within its time bounds,andfind corresponding times for the other events such that the set of times for all the events satisfy the interval constraints.TheB CPreference Imaging SlewingADFunctionFigure 2:Non-semi-convex Preference Function for the Landsatproblemcomplexity of this phase is (using the Bellman-Ford algorithm [Cormen et.al.,1990]).The main result of this discussion is that,while general TC-SPPs are NP-Complete,there are sub-classes of TCSPP prob-lems which are polynomially solvable.Important sources of tractability include the shape of the temporal preference func-tions,and the choice of the underlying semiring for construct-ing and comparing preference values.Despite this encouraging theoretical result,the extent to which real world preferences conform to the conditions nec-essary to utilize the result is not clear.To illustrate this,con-sider again the motivating example at the outset.As illus-trated in Figure 2,suppose an imaging event is constrained tooccur during,and that the interval is the inter-val during which a slewing event can start to occur.Assuming the soft constraint that prefers no overlap between the two oc-currences,the preference values for the slewing can be visu-alized as the function pictured below the interval,a function that is not semi-convex.A semi-convex preference function would result by squeezing one or the other of the endpoints of the possible slewing times far enough that the interval would no longer contain the imaging time.For example,removing the initial segment from the interval of slewing times would result in a semi-convex preference function.Dealing with the general case in which preference functions are not semi-convex is a topic of future work.6Related workThe merging of temporal CSPs with soft constraints was first proposed in [Morris and Khatib,2000],where it was used within a framework for reasoning about recurring events.The framework proposed in [Rabideau et.al.,2000]contains a representation of local preferences that is similar to the one proposed here,but uses local search,rather than constraint propagation,as the primary mechanism for finding good com-plete solutions,and no guarantee of optimality can be demon-strated.Finally,the property that characterizes semi-convex pref-erence functions,viz.,the convexity of the interval above any horizontal line drawn in the Cartesian plane around the func-tion,is reminiscent of the notion of row-convexity,used in characterizing constraint networks whose global consistency,and hence tractability in solving,can be determined by apply-ing local (path)consistency [Van Beek and Dechter,1995].There are a number of ways to view this connection.One way is to note that the row convex condition for the 0-1matrix representation of binary constraints prohibits a row in which a sequence of ones is interrupted by one or more zeros.Re-placing the ones in the matrix by the preference value for thatpair of domain elements,one can generalize the definition of row convexity to prohibit rows in which the preference values decrease then increase.This is the intuitive idea underlying the behavior of semi-convex preference functions.7SummaryWe have defined a formalism for characterizing problems in-volving temporal constraints over the distances and duration of certain events,as well as preferences over such distances.This formalism merges two existing frameworks,temporal CSPs and soft constraints,and inherits from them their gen-erality,and also allows for a rigorous examination of compu-tational properties that result from the merger.AcknowledgmentsThanks to David McAllister,Rina Dechter and Alessandro Sperduti for helpful comments in earlier stages of the devel-opment of this work.This work was partially funded by the Research Institute for Advanced Computer Science,NASA Ames Research Center,and by the EC TMR Network GET-GRATS (General Theory of Graph Transformation Systems).References[Bistarelli et al.,1997]S.Bistarelli,U.Montanari,andF.Rossi.Semiring-based Constraint Solving and Op-timization.Journal of the ACM ,44(2):201–236,March 1997.[Cormen et al.,1990]T.H.Cormen, C.E.Leiserson,andR.L.Rivest.Introduction to Algorithms .MIT press,Cambridge,MA,1990.[Dechter et al.,1991]R.Dechter,I.Meiri,and J.Pearl.Tem-poral constraint networks.Artificial Intelligence ,49,1991:61–95,1991.[Freuder and Wallace ,1992]E.C.Freuder and R.J.Wal-lace.Partial constraint satisfaction.Artificial Intelli-gence ,58,1992.[Mackworth ,1977]A.K.Mackworth.Consistency in net-works of relations.Artificial Intelligence ,8(1):99–118,1977.[Schiex et al.,1995]T.Schiex,H.Fargier,and G.Verfaille.Valued Constraint Satisfaction Problems:Hard and Easy Problems.In Proceedings of IJCAI95,pages 631–637.Morgan Kaufmann,1995.[Morris and Khatib ,2000]R.Morris,and L.Khatib.Rea-soning about Recurring Events:Satisfaction and Opti-mization.In Computational Intelligence ,16(2),2000.[Rabideau et al.,2000]G.Rabideau, B.Engelhardt anding Generic Preferences to Incrementally Improve Plan Quality.In Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space ,11–16,March,2000.[Van Beek and Dechter ,1995]P.Van Beek,and R.Dechter.On the Minimality and Global Consistency of Row-Convex Constraint Networks.In Journal of the ACM ,42,543–561,1995.。

Under consideration for publication in Theory and Practice of Logic Programming1 A Constraint Handling Rules Implementationfor Known-Arc-Consistency in Interactive Constraint Satisfaction ProblemsMARCO ALBERTI,MARCO GAVANELLI,EVELINA LAMMADipartimento di Ingegneria,Universit`a degli Studi di FerraraPAOLA MELLO,MICHELA MILANODipartimento di Elettronica,Informatica e Sistemistica,Universit`a degli Studi di Bolognasubmitted31July2002;revised26September2003AbstractIn classical CLP(FD)systems,domains of variables are completely known at the beginning of the constraint propagation process.However,in systems interacting with an external environment,acquiring the whole domains of variables before the beginning of constraint propagation may cause waste of computation time,or even obsolescence of the acquired data at the time of use.For such cases,the Interactive Constraint Satisfaction Problem(ICSP)model has been proposed as an extension of the CSP model,to make it possible to start constraint propa-gation even when domains are not fully known,performing acquisition of domain elements only when necessary and without the need to restart propagation after every acquisition.In this paper,we present a two sorted CLP language to express and solve ICSPs,and its implementation in the Constraint Handling Rules(CHR)language,a declarative language particularly suitable for high level implementation of constraint solvers.1IntroductionConstraint Logic Programming on Finite Domains(CLP(FD))represents one of the most successful implementations of declarative languages.By means of constraints, the user can give the specifications of a combinatorial problem and possiblyfind a solution,exploiting efficient propagation algorithms.CLP(FD)languages have been successfully used for solving a variety of industrial and academic problems.However, in some constraint problems,where domain elements have to be computed,it may not be opportune to perform the acquisition of the whole domains of variables before the beginning of the constraint propagation process.For instance,in configuration problems(Mailharro1998;Ilog1999)domain elements represent components,that have to be synthesized before being used.The set of components is not known beforehand,and sometimes even the size of the set cannot be estimated.Often a minimization of the set of components is required,thus the constraint solver produces a new component only when it is strictly necessary.In systems that need to interact with an external environment,domain elements can be produced by an acquisition system that retrieves information about the outer2M.Alberti et al.world.An example is given by Faltings and Macho-Gonzalez(2003)where Inter-net applications are faced and obviously not all the information can be computed before starting the constraint satisfaction process.As another example,consider a visual search system(Cucchiara et al.1999b)where domain elements are basic visual features(like segments,points,or surface patches)extracted from the im-age.In a classical CLP(FD)computation,all domain values must be known when defining the variables,so all the possible visual features would have to be extracted before starting the visual search process,even if only a small subset of them will be actually used.The synthesis of visual features is usually very time consuming,be-cause information encoded with signals must be converted in symbolic form.Thus, the extraction of domain elements that will not be used can result in a significant waste of computation time.Also,in systems that interact with an evolving environ-ment,full acquisition of all the domain elements is not wise(Barruffiet al.1999).In fact,if all the possible information is acquired beforehand,some of the information might be obsolete at the end of the acquisition.For all these reasons,a new model called Interactive Constraint Satisfaction Prob-lem(ICSP)has been proposed(Cucchiara et al.1999a)as an extension of the widely used Constraint Satisfaction Problem(CSP)model.In an ICSP,domains consist of a known part,containing the available elements,plus a variable that semantically represents a set of values that could be added to the domain in the future.In a sense, in an ICSP,domains can be considered as streams of information from one system to the constraint solver.Constraint propagation can be performed even with do-mains not completely known,and domain values can be requested to an acquisition system during constraint propagation;in other words,constraint propagation and value acquisition interact(thus Interactive in the name of the framework)and are interleaved,whereas in classical CSP frameworks domain elements are completely known before the beginning of the propagation.In this way,the acquisition system can possibly extract only elements consistent with the imposed constraints,thus fo-cusing the attention only on significant data.Various propagation algorithms have been proposed(Cucchiara et al.2001)for exploiting the available information and acquiring new domain values only when strictly necessary.Reducing the number of extracted elements can provide a notable speedup(Cucchiara et al.1999a).In(Gavanelli et al.2003)we describe a corresponding CLP language.Our lan-guage is two sorted.Thefirst sort is the classical sort on Finite Domains(FD). The second sort,called S-Channels,is based on a structure similar to streams,and represents domains of the FD variables.From the constraints on the FD sort,the system can start propagation before having full knowledge of domain elements. Each element will be inserted on demand in the domain,without having to restart constraint propagation from scratch.Moreover,constraints can be imposed on do-mains,thus helping the user defining S-Channels declaratively.In this paper,we provide an implementation of the language in Constraint Han-dling Rules(CHR).CHR(Fr¨u hwirth1998)is a declarative language for defining new constraint solvers at a very high level.CHR allows for rapid prototyping,and has proven effective in various real life applications.The purpose of this paper is to show how Constraint Handling Rules can be effectively used to implementA CHR Implementation for KAC in ICSPs3 the solver for our two sorted ICSP-based language.In previous works,the prop-agation algorithms have been proposed and separately implemented,but we did not describe the full implementation of the solver(Cucchiara et al.)for ICSP problems.The algorithms were implemented using non fully declarative constructs (e.g.,metaterms with destructive assignment).The encoding in CHR is higher-level, and more declarative.The implementation consists of a solver for the S-Channels sort,a solver for the FD sort and an interface between them designed to exploit the advantages of the ICSP model in systems interacting with external acquisition modules.Of course,other aspects in the model of a problem,besides domain elements, could be unknown:in a CSP there could be unknown variables or unknown con-straints.Typically,in all Constraint Programming systems new constraints can be easily added,while removal of constraints is more complex(Dechter and Dechter 1988).The addition of variables has been taken into account by Dynamic CSP models(Mittal and Falkenhainer1990).Our work is focussed on unknown domain elements,and proposes an interaction based on the acquisition,from an external system,of domain elements.The rest of the paper is organized as follows.The declarative and operational semantics of the language are described in Sections2and3,respectively.In Section 4some examples are shown.In Section5we describe the architecture of the language from an implementation viewpoint,and in Section6we show how it is implemented in the CHR language.Related works,conclusions and proposals for future work follow.2Syntax and Declarative SemanticsThe language described in this paper is based on a two sorted CLP,where thefirst sort is the classical sort on Finite Domains(FD)and the second is the sort on S-Channels.S-Channels are used both as domains for FD variables and as commu-nication channels with an external source providing elements.Wefirst define constraints and operations on the two sorts,then we link the two sorts.In the following,we comply to the conventions in(Jaffar et al.1998).In particular, every constraint domain C(where C can be FD,S-Channels or FD+S-Channels) contains:the constraint domain signatureΣC,the class of constraints L C(a set of first-orderΣ-formulas),the domain of computation D C(aΣ-structure that is the intended interpretation of constraints),the constraint theory T C(aΣ-theory that describes the logical semantics of the constraints),and the solver solv C.2.1The FD sortThefirst sort shares the same declarative semantics of the classical FD sort.Thus, the usual constraints in CLP(FD)are considered(arithmetic,relational constraints plus user-defined constraints).We suppose that the symbols<,≤,+,−,×,...be-long toΣF D and are interpreted as usual.4M.Alberti et al.2.2The S-Channels sortThe second sort provides domains for variables in thefirst sort.Domains are thus considered asfirst-class objects,and they can be declaratively defined by means of constraints.In a sense,they can be considered as streams,but they are in-trinsically non-ordered,and do not contain repeated elements.We call the sort S-Channels(Set-Channels).Declaratively,S-Channels are sets;thus unification and constraints should consider S-Channels terms modulo the set theory(Dovier et al. 1996):{A|{A|B}}={A|B},{A|{B|C}}={B|{A|C}},which states that sets do not contain repeated elements and order is not important.CLP(SET)(Dovier et al. 2000)and CLP(S-Channels)differ in the operational semantics and in the language expressiveness.Non-ground elements are forbidden in an S-Channel;this restriction allows for more efficient propagation algorithms.In CLP(S-Channels),the constraint domain signature,ΣS−Channel,contains the following constraints:•s-member(E,S)⇔E∈S•union(A,B,C)⇔A∪B=C•intersection(A,B,C)⇔A∩B=C•difference(A,B,C)⇔A\B=C•inclusion(A,B)⇔A⊆B2.3Linking the two sortsIntuitively,we want to bind CLP(FD)with CLP(S-Channels)with the intended semantics that S-Channels provide domains for FD variables.Given the two CLP languages L F D and L S−Channels,we define the CLP language L as the union of the two languages,with a further constraint,::,defined as follows:•the signatureΣ=ΣF D∪ΣS−Channel∪{::};•the intended interpretation D keeps the original mappings in the FD andS-Channel sorts;i.e.,D|ΣF D =D F D and D|ΣS−Channel=D S−Channel.The declarative semantics of the constraint isX::S↔X∈SThe symbol::is overloaded,and represents the usual CLP(FD)unary constraint linking a domain variable X to its domain when S is ground,and the binary con-straint of set membership when S is a channel.From the S-Channels viewpoint,it is just a set membership operator;its power comes from its operational semantics.3Operational SemanticsThe operational semantics of the language is defined by the propagation of con-straints in the two sorts,and the propagation of constraint::,linking them.Defining the operational semantics in this way will let us exploit the power of Constraint Handling Rules as a language for high level definition of constraintA CHR Implementation for KAC in ICSPs5 solvers:in fact,in some cases the rules written to actually implement the solvers result in a mere rephrasing to CHR syntax of those used to specify their semantics.3.1S-ChannelsThe semantics of the S-Channels sort is defined in terms of state of S-Channels, events over S-Channels and primitives used to modify the state.The state of an S-Channel is defined by its known part,i.e.the set of the elements which are known to belong to the S-Channel(as opposed to its unknown part, representing the elements which have not yet been acquired for the S-Channel), and its open-closed condition,i.e.,an S-Channel is open if new elements can be inserted into it,closed otherwise.A convenient notation to express the state of an S-Channel is one based on Prolog-like lists.An S-Channel is represented by a structure S defined as:S::={}S::={T|S}S::=Vwhere T is a ground term and V is a variable.The known part of the S-Channel is the set of all the ground elements in the list representing it;an S-Channel is closed if its continuation(tail)is ground,open otherwise.For example,S-Channel{1,2,3,4|T}is open,and its known part is the set{1,2,3,4};S-Channel{1,2,3,4}has the same known part,but it is closed. We have primitives to modify and check the state of a S-Channel.Two primitives are used to modify the state,namely:•ensure member(Element,Channel):ensures that Element is a member of the known part of Channel,possibly adding it if it is not already member,or failing if it is not already member and the S-Channel is closed;•close(Channel):closes Channel;after execution of this primitive,no new ele-ments can be added to the S-Channel;A Prolog-style definition of the primitives follows:ensure member(Element,):-var(Element),!,raise exception.ensure member(Element,Channel):-var(Channel),!,Channel={Element|},inserted(Element,Channel).ensure member(Element,{Element|}):-!.ensure member(Element,{|Tail}):-ensure member(Element,Tail).close({}).close({|T}):-close(T).6M.Alberti et al.Moreover,we have primitives to check the state of an S-Channel.•known(Channel,KnownPart):KnownPart is the list of elements in the known part of Channel.•is closed(Channel):checks if the Channel is closed.known(Channel,[]):-var(Channel),!.known({},[]).known({Element|TailS},[Element|TailK]):-known(TailS,TailK).is closed(Channel):-var(Channel),!,fail.is closed({}).is closed({|Tail}):-is closed(Tail).Predicate inserted(Element,Channel)in the second clause of the ensure member primitive is what we call an event:a notification of how the status of the computa-tion has been modified,which may be relevant for the rest of the computation and is to be processed properly.The semantics of an event is defined by rules specify-ing its interactions with the constraints in the store.It is quite apparent that the concept of eventfinds a natural representation as a CHR constraint;nevertheless, we prefer,in defining the operational semantics of the language,to keep events and proper S-Channels constraints distinct.In this case,the event is raised to interact with S-Channels constraints in the store and,if necessary,activate the propagation process which,by opportune prim-itives,will update the states of the S-Channels as necessary to ensure constraint satisfaction.The concept of event makes it possible to express the semantics of S-Channels constraints with simple(CHR-like)rules.For example,this rule is all that is needed to define the fact that,in the inclusion/2constraint,all elements in thefirst channel also appear in the second:inclusion(Channel1,Channel2),inserted(Element,Channel1)=⇒ensure member(Element,Channel2)This rule simply states that,if Element has been inserted into Channel1which is known to be included in Channel2,the propagation process must make sure that the element is also present in Channel2.This may imply the insertion of Element into Channel2,with a subsequent inserted(Element,Channel2)event,if Channel2is open and Element is not already a member,or a failure,if Channel2is closed and Element is not already a member.A CHR Implementation for KAC in ICSPs7 Propagation of closure can also be managed with ease.For instance,the following ruleinclusion(Channel1,Channel2),closed(Channel2),known(Channel1,K1),known(Channel2),K2)=⇒permutation(K1,K2)|closed(Channel1)(1)states that if Channel1⊆Channel2,Channel2is closed,and the known elements in Channel1are all the known elements in Channel2,then also Channel1is closed. Predicate closed/1is the event notifying that its S-Channel has been closed.3.2Link of the sortsIn the link of the two sorts,one must face the different understanding of the domain concept in the two sorts.In CLP(FD)systems,domains provide ancillary information about variables.Do-mains contain the possible values that a variable can take;if a value is not consistent with the imposed constraints,it is operationally removed from the domain.This helps many systems(Dincbas et al.1988;Puget1994;Aggoun et al.2001;Carlsson et al.1995)obtain high performance;in fact,domain wipe-outs are detected early and many alternatives are efficiently pruned.On the other hand,in the S-Channels sort,domains must be manipulated as logical entities:if an element is shown to semantically belong to a domain,it cannot be removed.Suppose that we have constraint{1,2,3}⊆D stating that the elements1,2and 3should belong to the set D,the constraint X::D that links variable X to the domain D,and X=1that states that X should be different ual constraint propagation of the constraint X=1would remove element1from the domain D,but this is inconsistent with the constraint{1,2,3}⊆D so the computation would fail.This behavior is not correct(remember that::declaratively means set membership),because the set of constraints{1,2,3}⊆D,X∈D,and X=1is satisfiable.This problem comes from a misunderstanding on the concept of domain.We need actually to make a distinction between the set of elements that semantically belong to the S-Channel,and the set of values that a variable can take,possibly belonging to a solution.For this reason,the domain of a variable X is represented by two streams:aDefinition Domain D dXthat contains all the values synthesized for the variable,and a stream of Removed Values D rX,that is the set of elements proven to be inconsistent with the imposed constraints.The set of available items for X,alsocalled Current Domain D cX,is given by the relation:D c X=D d X\D r X·(2)It should be noticed that D cX remains open until D dXis closed.D rX,instead,is alwaysopen,so to make it possible to move elements into it from the current domain even if the definition domain is closed.8M.Alberti et al.Fig.1.FD Constraints asfilters on variable domainsWith the imposed constraints,one can declaratively add a newly synthesized value to the definition domain(imposing the constraint v∈D dX)or remove aninconsistent element from the current domain(w/∈D cX or,equivalently,w∈D rX;see Fig.1).In this way,during search,an inconsistent element will not be tried if itbelongs to D rX and a possible domain wipe-out will be detected when D cXis empty.With this representation,FD propagation can be implemented without affecting the S-Channels sort;in fact,FD propagation only influences the current domain and the stream of removed values,while propagation on domains only affects the definition domain.Note that the relation in Eq.2automatically propagates two types of information from the definition domain to the current domain of a variable.First,whenever a domain element is synthesized,it is considered in the current domain and can be exploited for propagation.Second,if no more values are available to the definition domain,also the current domain becomes closed.Notice that more than one FD variable can range on the same definition domain or,equivalently,their definition domains can be linked by an equality constraint; however,each of them will have its own current domain and set of removed values.The user can write,e.g.,X::D dX ,Y::D dYand D dX=D dY,meaning that the twovariables X and Y semantically range on the same set of elements.Nevertheless,to X a current domain D cX and a set D rXof removed values will be associated,andto Y the two sets D cY and D rY.On the sets the following relationships hold(by Eq.(2)):D cX =D dX\D rXand D cY=D dY\D rY.Notice that,by definition,the user cannot close the current domain of a vari-able:the user should not access directly the current domain,but only the definition domain.We believe that this is not a restriction,because if one wants to close inde-A CHR Implementation for KAC in ICSPs9 pendently the current domain of different variables(as in the previous example),he can define two different definition domains(and,possibly,impose some constraintsamong them,e.g.,D dX ⊆D dY).3.2.1Guided AcquisitionIn some applications constraints can be used not only for removing inconsistent values from the current domains,but also for guiding the acquisition.In fact,if the acquisition module that provides values to the solver is able to take some constraints into account,these constraints can be used to acquire only consistent values.This can provide a huge performance improvement,but,as is explained later in this section,it can be exploited only if we do not impose any constraint on the definition domains.Constraints on FD variables limit the possible combinations of assignments.Op-erationally,they prevent inconsistent elements from entering the current domain. If we want to perform a guided acquisition,FD constraints can also play a second role:provide the acquisition module with the corresponding auxiliary constraints which can be used to acquire only consistent values.Auxiliary constraints avoid inconsistent element to enter in the definition domain.Definition3.1A constraint c(X i,X j)defines two auxiliary constraints c u i(U c i,X j)and c u j(X i,U c j).c u i(U c i,X j)is a subset of the Cartesian product P(D c i)×D c j rep-resenting couples of compatible assignments of the sub-domain U c i⊆D c i and the variable X j∈D c j.It is satisfied by a couple of assignments U c i=S i⊆D c i,X j=v j iff∀v i∈S i,(v i,v j)∈c(X i,X j).For example,an FD constraint c(X i,X j)removes inconsistent elements from the domain(i.e.,puts the elements in the Removed Values stream)and can impose the auxiliary constraints c u j(X i,U c j)and c u i(U c i,X j).A constraint like c u j(X i,U c j)is a relation between an object and a set of objects,linking every domain element with a subset of the second domain.For instance,a constraint X>5,where X::D and D={1,10|U},produces the new domain{10|U }with the imposed constraint ∀v∈U ,v>5.An auxiliary constraint can only be imposed by an FD constraint(it is not accessible at the language level).Unluckily,it is not always possible,in general,to ensure that the auxiliary con-straints will influence the synthesized elements and completely avoid the inefficient generate-and-test generation of new domain elements.However,in various real-life cases it is possible to select a subset of auxiliary constraints that can be exploited by the generator of domain elements.For example,the acquisition system might be able to handle only linear con-straints.In this case,if the constraint solver asks for an element v such that v>3 and v2<20the generator could take into account only thefirst,and reply v=5. The auxiliary constraint v2<20will then redirect the value5to the set of removed values and ask for another element.In other words,some of the constraints can be10M.Alberti et al.used only for checking and others also for generating new elements.Other examples will be given in Section4.However,auxiliary constraints can only be used if the user is interested in con-sistent current domains,but not in complete definition domains:in fact,auxiliary constraints can prevent elements that logically belong to definition domains from being acquired.3.3Operational Semantics:Finite DomainsSince we want to avoid useless value acquisition,we use a constraint propagation based on the available knowledge,when domains are still partially specified.For this reason,we propose an extension,for the partially known case,of the concept of consistency,called known consistency.In this paper,we provide only the defi-nition of node-consistency and arc-consistency;the extension to higher degrees of consistency is straightforward.Definition3.2A unary constraint c(X i)is known node-consistent iff∀v i∈K c i,v i∈c(X i),where K c i is the known part of the domain of X i.Definition3.3A binary constraint c(X i,X j)is known arc-consistent iff∀v i∈K c i,∃v j∈K c j s·t·(v i,v j)∈c(X i,X j),where K c i and K c j are the known parts of the domains of X i and X j,respectively.Definition3.4A constraint network is known arc-consistent(KAC)iffall unary constraints are known node-consistent and all binary constraints are known arc-consistent. Known Arc-consistency,like Arc-Consistency(AC)(Mackworth1977)is a prop-erty of a constraint graph.Besides the property,various algorithms have been pro-posed to achieve arc-consistency(Waltz1975)(Mackworth1977)(Mohr and Hen-derson1986)(Hentenryck et al.1992)(Bessi´e re1994)(Bessi´e re et al.1999),i.e., to obtain a problem equivalent to the original one,in which the property holds. All these algorithmsfilter the domains(Waltz1975)and provide a sub-domain, i.e.,a restricted set of domains for the CSP variables.More precisely,they pro-vide the maximal arc-consistent sub-domain,i.e.,the biggest sub-domain which is arc-consistent.In the same way,there are many algorithms that translate a problem,P,into an equivalent problem P ,with different domains,such that the new problem P is KAC.The following proposition explains the outcome of an algorithm achieving KAC:A CHR Implementation for KAC in ICSPs11Lemma1If a network of constraints is KAC,then the subset of known elements is an arc-consistent sub-domain.Proposition1Every algorithm achieving KAC(i.e.any algorithm that computes an equivalent problem that is KAC)and that ensures at least a known element in each vari-able domain is able to detect inconsistency in the same instances as an algorithm achieving AC.Proofs can be found in(Gavanelli et al.2003).In other words,if there exists an arc-consistent sub-domain,then there exists a maximal arc-consistent sub-domain;so if KAC does not detect inconsistency,AC will not detect inconsistency either.KAC is equivalent to AC when domains are completely known.The advantage in using KAC is that the check for known arc-consistency can be performed lazily, without full knowledge of all the elements in every domain.Operationally,achieving KAC has some similarities with achieving Lazy Arc Consistency(LAC)(Schiex et al.1996).LAC is an algorithm thatfinds an arc-consistent sub-domain(not necessarily a maximal one)and tries to avoid the check for consistency of all the elements in every domain.KAC looks for an arc-consistent sub-domain as well,but it is aimed at avoiding unnecessary information retrieval, rather than unnecessary constraint checks.In order to achieve AC,algorithms need to remove elements that are proven to be inconsistent.In order to achieve KAC,algorithms need to remove elements and to promote elements,i.e.,to move ideally some elements from the unknown part to the known part.Elements can then be removed(i.e.,prevented from entering the current domain)if they are shown to be inconsistent.An algorithm for achieving KAC is shown in(Gavanelli et al.2003).It is worth noting that the addition,besides the deletion,of elements to the cur-rent domain might seem non monotonic.However,the current domain is kept open as long as new acquisitions are possible(i.e.,until the definition domain is closed), the unknown part representing the set of future acquisitions.Thus,declaratively, when a new element enters the known part of the current domain,it is not properly added:it is just made explicit.A similar behavior is also achieved by Mailharro (1998)with the use of a Wildcard representing values entering the domain. Clearly,the repeated acquisition of the same element would result in a loop. This problem can be avoided either by passing the set of already acquired values (the known part of the definition domain)as inconsistent to the acquisition module (if this supports auxiliary constraints,see Sect.3.2.1)or by having an acquisition module that does not provide twice the same element to the same S-Channel(as hypothesized,for instance,by Mailharro(1998)).However,in general,if no hy-potheses are made about the behaviour of the acquisition module,then it is not possible to guarantee the absence of loops.。

SCIENCE &TECHNOLOGY VISION 科技视界0引言随着高校规模的不断扩大、专业的不断扩充、以及教学设施的不断完善,教务管理工作的难度逐年加大,作为教务管理关键工作之一的课程编排问题也成为了当前教务人员所面临的复杂问题。

杨林根[1]提出了基于免疫遗传算法的排课问题解决方案,但未考虑课程对于教学楼的特殊要求;王超[2]针对机房排课问题,设计了改进的离散粒子群算法进行求解;针对中职院校的排课需求,张燕芬[3]提出了一个基于银行家算法和贪心算法的排课算法;针对高职院校的排课特点,吴小丽[4]对排课系统的基本功能模块和主要和新算法实现进行了研究与分析。

约束满足是一种组合优化问题的建模与求解技术,它能以更加接近现实世界的方式描述调度问题及其约束,在约束求解中,能够充分利用问题的结构信息、约束关系,采用约束传播、回溯、搜索等技术对求解空间快速缩减,提高问题的求解效率。

本文考虑了高等院校的排课问题对于不同教学楼的特殊需求,将其映射为一类约束满足问题,进而建立以最优化教室负荷均衡性为目标的约束满足优化模型。

针对模型中硬性约束和柔性约束并存的特殊情况,设计了问题的约束满足求解算法。

1排课优化模型1.1问题描述高校排课问题是在课程及任课教师已定的情况下,为每一门课程选定适当的教室和时间,以确保教学计划的正常进行。

在排课过程中,应当综合考虑教室、教师、时间等资源的限制,遵循以下原则:1)同一个班级的不同课程不允许安排在同一时间。

2)同一名教师的不同课程不允许安排在同一时间。

3)同一个教室在同一时间只允许至多安排一门课程。

4)教室能容纳的学生数不小于在该教室上课的人数。

5)同一门课程不允许在同一天内连续上两节或两节以上。

此外,由于高校是具有多学院、多专业的高等院校,每个学院往往是有其专门的学院楼,因此,在排课过程中应尽量满足学院、教师、教室、班级等特殊需求,例如:课程指派应尽可能的分散在不同的教室;专业课应主要安排在该学院所在的教学楼内的教室进行,公共课则必须安排在公共教学楼;尽量满足个别教师教课时间的特殊要求。

Tudor Hulubei,Eugene C.Freuder and Richard J.WallaceDepartment of Computer Science,University of New HampshireDurham,New Hampshire,USACork Constraint Computation Centre,Computer Science DepartmentUniversity College Cork,Cork,IrelandCorresponding author:Richard J.Wallace,Cork Constraint Computation Centre, University College Cork,College Road,Cork,Irelandphone:00353-021-425-5409,fax:00353-021-425-5424,email:r.wallace@4c.ucc.ie,Reprint requests to:Eugene C.Freuder,Cork Constraint Computation Centre, University College Cork,College Road,Cork,Irelandphone:00353-021-425-5401,fax:00353-021-425-5424,email:e.freuder@4c.ucc.ie, short title:Goldilocks Problemmanuscript pages:36,figures:8AbstractConstraint-based reasoning is often used to represent andfind solutions to con-figuration problems.In thefield of constraint satisfaction,the major focus has been onfinding solutions to difficult problems.Many real-life configuration prob-lems however,while not extremely complicated,have a huge number of solutions, few of which are acceptable from a practical standpoint.In this paper we present a value ordering heuristic for constraint solving that attempts to guide search to-wards solutions that are acceptable.More specifically,by considering weights that are assigned to values and sets of values,the heuristic can guide search towards solutions for which the total weight is within an acceptable interval.Experiments with random constraint satisfaction problems demonstrate that,when a problem has numerous solutions,the heuristic makes search extremely efficient even when there are relatively few solutions that fall within the interval of acceptable weights. In these cases,an algorithm that is very effective forfinding a feasible solution to a given constraint satisfaction problem(the“maintained arc consistency”algo-rithm,or“MAC”)does notfind a solution in the same weight-interval within a reasonable time when it is run without the heuristic.keywords:constraint satisfaction,configuration,heuristics1Introduction“So away upstairs she went to the bedroom,and there she saw three beds.There was a very big bed for Father bear,but it was far too high.The middle-sized bed for Mother bear was better,but too soft.She went to the teeny,weeny bed of Baby bear and it was just right.”–Goldilocks and the Three Bears.In recent years,constraint satisfaction has become an important means of modeling some of the critical features of configuration problems(Wielinga& Schreiber,1997;Sabin&Weigel,1998).Given the ubiquity and difficulty of handling constraints between the components of a configuration problem this is perhaps not surprising.In addition,this form of representation allows a clear sep-aration of representation and control,in the form of search,and there are now many powerful search algorithms that can be applied to any problem represented in these terms.Because configuration problems are often under-defined it may be easy tofind a solution.(That this is a not uncommon situation is attested to by the experience of thefirst author in a commercial setting.)Unfortunately,many of these solutions may be undesireable for a variety of reasons that fall outside the scope of the basic model and it may be impossible to examine all of them.Practical problems also often involve a reconfiguration step,so that a product can meet additional specifications.In such cases it may be desireable from the vendor’s point of view to“upsell”to a related but more expensive product.This3may also suit the user if he or she is now more knowledgeable about the product and is,therefore,looking for greater functionality.This process may be consid-ered as an iterative approach to“mass customization”(Felfernig et al.,2001), necessitated by the requirements of knowledge acquisition.In either case we are faced with the same situation that Goldilocks was but with a lot more options to consider.Since we don’t know if any of them will be exactly right,we are willing to be somewhatflexible about our interpretation of “just right”,and stop our testing when wefind a solution that is“good enough”. In particular,when solutions can be ordered along a certain dimension,we may want to look for solutions at a desired point along that scale.There may not be a solution at that exact point,or it may be too costly to search until wefind an exact match,so we are willing to specify a tolerance range around that point in which to search.In this paper,we will present an algorithm that is good atfinding a solution within such a range.Most search algorithms use heuristics to guide search towards those regions of the search space that are more likely to contain solutions.For constraint sat-isfaction algorithms,the most common types of heuristics involve selecting the element to consider next,e.g.the next component,and then selecting a value to assign to that element.In a configuration task,for example,we might decide to consider a component that can only take on a few values before selecting one that can take on many.This is,in fact,an example of the“minimum domain size”4heuristic that is well-known in the constraint satisfaction literature.When solving a particular class of problems,in addition to relying on general purpose heuris-tics,class-specific heuristics can be used to take advantage of the structure of the class at hand.For example,we may decide to establish the value for the size of a container before selecting values related to components that are to go inside this container.In this paper we will describe a value ordering heuristic that can be used if each element of the problem has an associated weight or rating.The object is to find a solution that is within some pre-specified range for the aggregated weight of the entire problem.(This work is a revision of an earlier report by Hulubei& Freuder(1999).)The next section introduces the main idea with a simple example.Section 3gives some background definitions for the problem.Section4describes the heuristic.Section5discusses interpretations of solution weights and possible applications of this approach to problem solving.Section6gives results of some experiments on random test problems in which the new heuristic is compared with one of the most efficient general algorithms for constraint satisfaction problems. Section7discusses extensions to the present methods.Section8gives conclu-sions.52An ExampleThe following example will give a short preview of the things that are going to be discussed in the next sections.Consider a small configuration problem consisting of three variables and two binary constraints(Figure1).Both the values that can be assigned to a variable,and the sets of values(tuples)allowed by the constraints have associated weights,because the acceptability of a solution is usually influ-enced by both the quality of the values chosen and the resulting associations of values.——————————————————————-INSERT FIGURE1ABOUT HERE——————————————————————-The weight of a solution to this problem is defined as the sum of the weights of all values and pairs of values involved in the solution.We can easily see that=1,=1and=-1is a solution to our problem,and its weight is(0.8+0.1+0.8)+(0.7+0.5)=2.9.We can compute lower and upper bounds for the solution weight,by summing up the minimum and maximum weights in each variable and constraint.In our example,the lower bound is MinSW=(0.2+0.1+0.8)+(0.1+0.2)=1.4,and the upper bound is MaxSW=(0.8+0.7+0.9)+(0.9+0.5)=3.8.That is,no solution weight can be smaller than MinSW or greater than MaxSW.As we will see next,MinSW and6MaxSW are theoretical limits,i.e.solutions with these weights might not exist. 3Background Concepts and DefinitionsFollowing Mittal and Frayman(Mittal&Frayman,1989),we can define a config-uration problem as as set of components,each with certain properties,and ports that connect components.Both components and ports can be considered as vari-ables in a constraint satisfaction problem.In addition,there are constraints that restrict the ways that components can be combined in a solution(cf.Sabin& Weigel,1998).A constraint satisfaction problem(CSP)can be defined as a tuple, consisting of a set of variables a variable involved in,a set of do-mains,where each domain is itself a set is a value that can be assigned to,with,and a set of constraintsa constraint between and.Each constraint defines a set of pairs of values that are allowed by the constraint.That is,and is allowed by the constraint.If a pair then that pair is not allowed by the constraint.A solution to the problem is a set of valuess.t.,.A partial solution consists of a set of valuess.t.,and,7.A CSP with weights can be defined as a tuple,where, ,and are defined as before,and there is also a set of weights such that each value has an associated weight,and each pair of values has an associated weight.Note that,if,then all the possible pairs of values from and are implicitly allowed,but their weights are undefined.We define the weight of a solution as the sum(over all the variables and constraints)of the weights of all the values and pairs of values involved.For-mally,with,and .The weight of a partial solution is defined similarly,with the exception that only variables included in the partial solution and the constraints among them are taken into account.For each variable we can compute the range of possible weights by simply taking the minimum and maximum weights among all the values in the domain of that variable.For all s.t.,and:Similarly,for each constraint we can compute the range of possible weights by taking the minimum and maximum weights among all pairs of values al-lowed by the constraint.For all s.t.8,and:.Lower and upper bounds for the weight of a solution to are computed as:.Note that there might be no solutions with these weights,all we are saying here is that.In order to compute the exact minimum and maximum solution weights we would have to look at all the solutions.4The“acceptable-weight”HeuristicOne way of looking for solutions with weights in a given range is to simply use a general purpose search algorithm and every time a solution is found check whether or not its weight is within the acceptable range.However,since it does not use the weights during search,such an algorithm will look for any solution,leaving to chance the discovery of an acceptable one.The acceptable-weight value ordering heuristic is an attempt to do better than that by guiding search towards areas of the search space that are likely to contain solutions with acceptable weights.9Consider a problem and two positive real numbers,and, representing the minimum and maximum acceptable solution weights,with.A solution is acceptable if:.Given the range of acceptable solution weights,we con-sider the ideal solution weight()as being at the center of that range. (Obviously,we can also start with an ideal weight and define a range of accept-able weights around it.)During search,a constraint that involves at least one variable that has not been instantiated(i.e.assigned a value)is considered active,while a constraint that in-volves only instantiated variables is considered inactive.This distinction is useful when computing the weight of a partial solution,since only instantiated variables and inactive constraints can be considered.For brevity,we define the weight ofan instantiated variable as the weight of the value that has been assigned to it,and the weight of an inactive constraint as the weight of the pair of values assigned to the variables involved in that constraint.The idea behind acceptable-weight is to keep track of the weight of the current partial solution and attempt to obtain a solution for the rest of the prob-lem whose weight,combined with thefirst one,will bring the global solution weight as close to as possible.Based on,the number of currently10uninstantiated variables,and,the number of currently active constraints in the problem,acceptable-weight computes the average of the individual weights ()that these variables and constraints would contribute to the global solution weight,should it equal:IdealSW sw S——————————————————————-INSERT FIGURE2ABOUT HERE——————————————————————-In this example,search is at the point of instantiating.The possible values are1(whose weight is0.4)and5(whose weight is0.8),and the acceptable-weight heuristic is supposed to suggest one of them.Let us take a look at the implications of selecting each value,assuming that at this point in the search.In this example,and.If we choose to assign to,then. If we choose,then.After computing,we see that selecting the value will yield a weight for that is closer to .After the assignment of,acceptable-weight recomputes the ,to compensate for the amount we were off.The strategy behind the heuristic described is two-fold.Locally,we try to make sure that each small subproblem centered around the current variable has a weight that is in line with the global.Globally,by constantly adjusting the we try to control the overall deviation of the solution weight.Note that the algorithm is still complete;if search backs up due to failure,the acceptable-weight heuristicfinds the value with the best weight from among the remaining12values in a domain.This strategy appears to work well in practice,as we will see in Section6.5Interpretation and Use of Solution Weights Clearly,solution weights as used in this paper cannot be taken to represent pref-erences directly,since typically we do not search for solutions with the maximum weight.They can be related to preferences by considering distances between a given solution weight and the ideal weight;the greater this distance,the lower the preference.This kind of interpretation has considerable psychological support,at least for simple sensory dimensions(Coombs&Avrunin,1977).Since a solution weight is the sum of many individual weights,one inter-pretation of it is as a summary quality,for example price.When we use the acceptable-weight heuristic,we are trying to focus on one subrange of values for this quantity.In terms of our criterion for acceptance,we are making a“strong homogeneity assumption”,that any combination of weights yielding a given sum is equally acceptable.Note that the heuristic itself will bias sampling from this set in favor of solutions with individual weights closer to the average.However,this is still consistent with our assumption since any solution within this set is equally acceptable.As already noted,a potentially important application of this approach is“up-13selling”,in which we start from a given product or configuration and search for related systems that are higher in price.We do not necessarily know which com-bination of new values will be most satisfactory,but we want to narrow the search to those having a certain difference in price from the original entity.The idea of preferrable distance can be extended to other global measures, such as complexity or simply magnitude(larger,and/or faster,and/or greater ca-pacity,etc.).In addition,in these cases as well as for price,we can either focus on some a priori ideal point or search for a possible ideal point that the user might already have.The acceptable-weight heuristic is nicely suited to these kinds of tasks, since it allows one to choose a given weight as an ideal,which it then zeros in on.Because it takes a heuristic approach,it has the potential tofind solutions quickly(cf.next section),in contrast to more laborious optimization procedures like branch-and-bound for MAX-CSPs(Jampel et al.,1996).In these cases,derivation of weights for domain values can be done automati-cally by considering the difference between a value that serves as the origin point and the present value for that variable.The initial solution may be obtained by the customer through an interactive strategy,such as constraint-based matchmaking (Freuder&Wallace,2002).Alternatively,an‘original’solution can be chosen by the system on an a priori basis.Constraint weights can be derived in accor-dance with the value weights,i.e.to maximize the likelihood that values with the14appropriate weights will be ers can influence this process directly by specifying ideal values for certain variables or variable combinations.Or they can simply characterize an ideal solution,for example in terms of a difference in price, from which individual weights can be derived.6Experimental ResultsThe acceptable-weight heuristic has been tested sucessfully on a small PC-configuration model(built according to specifications provided by Concentra, Inc.,now part of Oracle,Inc.).However,in order to evaluate its performance more systematically we performed experimental tests on problems that were randomly generated(random CSPs).This allowed us to test the ability of this heuristic to find solutions in weight-ranges with diminishing numbers of solutions.Problems were generated using a“probability of inclusion”model withfixed numbers of elements.Under the probability of inclusion model,any element of each type(constraints,domain values,or constraint tuples)is included in the prob-lem with a stipulated probability;in thefixed version,in addition,the whole pro-cess is repeated until the number of elements actually chosen is the same as the expected number of such elements given this probability.For example,if there is a constraint between two variables both with domains of size four and the stip-ulated probability of inclusion of a constraint tuple is0.75,each of the possible1516tuples is considered for inclusion using a probability of0.75,and the process is repeated(each time from scratch)until the number of tuples in the constraint =12.For each value and constraint tuple,a weight was also chosen at random within the range[0,1].For the present tests we used the“maintained arc consistency”,or MAC al-gorithm(Sabin&Freuder,1994).This algorithm is a form of backtrack search, where search is interleaved with consistency maintainence among the domains of variables that are not yet instantiated.Specifically,after each selection of a vari-able and a value for assignment,the domains of all the uninstantiated variables are made pairwise consistent,or“arc consistent”(Mackworth,1977).This means that for any pair of variables linked by a constraint,each value in one of the do-mains is supported by at least one value in the other domain.(Hence the name,“maintained arc consistency”.)This algorithm is part of a constraint satisfaction library developed at the University of New Hampshire,which is freely available at /tudor/csp.Our tests compared the performance of MAC+acceptable-weight with that of MAC.In both cases we used a standard arc consistency algorithm known as AC-3and the dynamic minimal domain size variable ordering heuristic.The algorithms were used tofind acceptable solutions to problems with100variables, each variable having5values in its domain.All the instances we tested had very similar behaviour,and we chose one of them to show in each of the experiments16presented here.The reason for showing just one problem instance in Figures3-7 is that we were interested in comparing different intervals of acceptable weights for each problem.The constraint density(defined as the fraction of the possible constraints be-yond the minimum,that the problem has)and the constraint tightness(de-fined as the fraction of all possible pairs of values from the domains of two vari-ables that are not allowed by a constraint)were used to vary the difficulty of the generated problems in order to study changes in the behaviour of acceptable-weight.In the following tests we will compare the time required by the two algorithms tofind an acceptable solution.Both algorithms will look for solutions in ranges of a given size(0.05and0.1in the examples below)centered around the solution weight on the X axis,which has been translated and scaled fromto.We set a timeout limit at6seconds,since we were interested in the performance of algorithms that could be used in an in-teractive setting,as well as algorithms that couldfind a series of solutions close to a desired weight in a short time period.——————————————————————-INSERT FIGURE3ABOUT HERE——————————————————————-Before going any further,we need to briefly explain the behaviour of MAC on these problems.Without going into details,we will just say that,probabilistically17speaking,there are many solutions with weights around0.5and very few solutions with extreme weights(close to0or1).MAC does not take weights into account, and thus from its point of view solutions are distributed throughout the search space.However,since most solutions have weights around0.5,MAC will tend to find those pretty quickly.Thefirst test we did was with density=0and tightness=0.Figure3shows the performance difference between the two algorithms.While MAC can onlyfind solutions with weights in the range,0.455-0.54,MAC+acceptable-weight is capable offinding solutions with weights in the range,0.226-0.79.Moreover, in most cases the veryfirst solution that MAC+acceptable-weightfinds is within the acceptable range.The test in Figure4was similar to the one in Figure3except that the con-straint tightness has been increased to0.25.As a result,the range in which MAC+acceptable-weight canfind acceptable solutions decreases slightly to 0.244-0.752.The range in which MACfinds acceptable solutions also changes a little,to0.469-0.560.——————————————————————-INSERT FIGURE4ABOUT HERE——————————————————————-Thefirst two results presented were performed with ranges of size0.05.That is,any solution with a weight that differs in absolute value by at most0.025from18the ideal weight was considered acceptable.As we widen the acceptable range, the interval in which both algorithms quicklyfind solutions widens.In the test pic-tured in Figure5,MAC was capable offinding acceptable solutions with weights in the0.444-0.584range.MAC+acceptable-weight performed much better, covering the0.216-0.798range(also note that this improves on the0.244-0.752 range in Figure4).——————————————————————-INSERT FIGURE5ABOUT HERE——————————————————————-In our fourth test,we increased the constraint graph density while keeping the tightness at0.25and the range at0.1.In this test(Figure6),MAC alone cov-ered the0.447-0.569range while MAC+acceptable-weight covered0.415-0.568(the spike around0.601marks a small region where MAC+acceptable-weight found acceptable solutions;with a longer time limit it would have cov-ered the0.568-0.601range as well).Thus,as the problems get harder,the impact of acceptable-weight be-comes less noticeable.In terms of weights,the density of solutions is given by a normal distribution.The reason for the performance degradation is that as den-sity and/or tightness increase,the number of solutions decreases,and the areas affected the most are those at the sides of the normal distribution curve,which contain a very small number of solutions to begin with.Gradually,the range cov-19ered by MAC+acceptable-weight will shrink to a range comparable to that covered by MAC alone(Figure6),because there will be virtually no solutions outside a small range around0.5and MAC will be able tofind those equally fast just by looking for any solution.——————————————————————-INSERT FIGURE6ABOUT HERE——————————————————————-For the problems tested here(100variables,domain size5),the difficulty peak (Cheeseman et al.,1991)for tightness=0.25is around density=0.0651(Figure8). Around this peak MAC+acceptable-weight still compares well with MAC (Figure7).It should be noted,however,that we are not targeting hard problems with this heuristic.As stated earlier,configuration problems are often relatively easy,so there are lots of solutions;the challenge is tofind one that is acceptable.——————————————————————-INSERT FIGURE7ABOUT HERE——————————————————————-These experiments show that the acceptable-weight heuristic is able to find solutions even if there are relatively few candidates,in contrast to ordinary CSP algorithms.The speed with which solutions were found(generally under120second)for problems of this size supports the contention that this heuristic ap-proach will often outperform optimization-based approaches(cf.Jampel et al., 1996).Since there was typically a very sharp transition between the region where problems were found quickly and regions where locating problems was quite dif-ficult,it is clear that similar results would be found even if the cutoff time was reduced to as little as one second.7Future WorkOne way to improve the performance of the heuristic might be by trying to detect situations where search gets stuck in a given range.There are situations where MAC+acceptable-weight obtains a partial solution,but there is no way of extending it to a complete solution with an acceptable weight.It is clear that in those situations the heuristic has made a few mistakes,and it might be inter-esting to see if the overall performance can be improved by refusing to listen to the heuristic’s suggestions until the range of solution weights obtained changes. Somewhat related ideas can be found in(Harvey&Ginsberg,1995).——————————————————————-INSERT FIGURE8ABOUT HERE——————————————————————-21Another idea would be to avoid searching in subtrees where there is no way of extending the current partial solution to a complete solution with an acceptable weight.Rough estimates of the potential contribution of the unsolved part of the problem can be obtained by computing its minimum and maximum solution weights(and).In addition,we may be able to obtain better weight evaluations for the small subproblems centered around the current variable. In particular,we would like to be able to take future variables into account in this process.Another reasonable extension is to conditional or dynamic CSPs,where the inclusion of variables or constraints in a problem may depend on prior instantia-tions,especially since this variant of the constraint satisfaction problem was de-veloped for use with configuration problems(Mittal&Falkenhainer,1990).Since the acceptable-weight heuristic uses a moving average,it should be possible to adapt it to problems that change dynamically.At the same time,this is another case where it would be useful to be able to take future variables into account when calculating weight evaluations during search.8ConclusionsGoldilocks learned a very important lesson.There are things in life that are not the “right size”for everyone.It is often the case that there is a wide range of choices22to pick from,and we have to determine which one is“too big”,“too small”,or “just right”.Worse still,we sometimes have to relax our notion of“just right”,to get something that is“good enough”.One of the most exciting trends in product configuration involves the application of this lesson to product development,under the banner of“mass customization”(Felfernig et al.,2001).The acceptable-weight heuristic presented here has obvious relevance for this effort,since it is designed to guide search towards solutions with acceptable weights,when solutions can be ranked along a given dimension.Although we believe there are avenues for improvement,our experiments have shown that this heuristic,combined with MAC,canfind acceptable solutions very quickly across a fairly wide range of target values.AcknowledgementsThis material is based on work supported by Oracle Corporation and by the Na-tional Science Foundation under Grant No.IRI-9504316and carried out while the authors were in the Department of Computer Science at the University of New Hampshire.Work on the paper was supported in part by Science Foundation Ire-land under Grant00/PI.1/C075.The second author is currently supported by a Principal Investigator Award from Science Foundation Ireland.Several parts of this paper were improved by the comments of the anonymous reviewers.23。

/locate/ijpeAuthor’s Accepted ManuscriptComputing core allocations in cooperative gameswith an application to cooperative procurementJ.Drechsel,A.KimmsPII:S0925-5273(10)00268-9DOI:doi:10.1016/j.ijpe.2010.07.027Reference:PROECO 4490To appear in:International Journal of Production Economics Received date:31March 2009Revised date:9December 2009Accepted date:16July 2010Cite this article as:J.Drechsel and A.Kimms,Computing core allocations in cooperative games with an application to cooperative procurement,International Journal of Production Economics ,doi:10.1016/j.ijpe.2010.07.027This is a PDF file of an unedited manuscript that has been accepted for publication.As a service to our customers we are providing this early version of the manuscript.The manuscript will undergo copyediting,typesetting,and review of the resulting galley proof before it is published in its final citable form.Please note that during the production process errors may be discovered which could affect the content,and all legal disclaimers that apply to the journal pertain.Computing Core Allocations in Cooperative Gameswith an Application to Cooperative ProcurementJ.Drechsel and A.KimmsAddress of correspondence:Julia Drechsel and Prof.Dr.Alf KimmsLehrstuhl f¨u r Logistik und VerkehrsbetriebslehreMercator School of ManagementUniversity of Duisburg–EssenLotharstr.65·47048Duisburg·Germanyemail:julia.drechsel@uni–due.deemail:alf.kimms@uni–due.deURL:http://www.msm.uni–due.de/log/Computing Core Allocations in Cooperative Games with an Application to Cooperative ProcurementAbstractCooperative game theory defines several concepts for distributing outcome shares in a cooperative game with transferable utilities.One of the most famous solutionconcepts is the core which defines a set of outcome allocations that are stable suchthat no coalition has an incentive to leave the grand coalition.In this paper wepropose a general procedure to compute a core element(or to detect that no coreallocation exists)which is based on mathematical programming techniques.Theprocedure proposed in this paper can be applied to a wide class of cooperativegames where the characteristic function is given by the optimum objective functionvalue of a complex optimization problem.For cooperative procurement,which is anexample from thefield of supply chain management where some literature on thecore concept already exists,we prove the applicability and provide computationalresults to demonstrate that games with150players can be handled.Keywords:cooperative game theory,core,mathematical programming,procurement, lot sizing,inventory games,supply chain management1IntroductionIf several players cooperate,one of the most important questions is how to distribute the outcome shares.As one example from the real world,we refer to business networks(see Lo Nigro and Abbate,2009)where sharing is a topic.Let us assume that the outcome is a transferable utility such as money,for instance.For the sake of simplicity we will use the term cost instead of outcome to have an illustrative wording with the understanding that players prefer lower outcomes.In other settings the outcome could be a profit contribution, for instance,so that players prefer higher outcomes,but it is straightforward to adapt the following material to such situations.Cooperative game theory provides several concepts to define the outcome shares and one concept,the core,which is in widespread use shall be discussed here:Let N be the given set of players andπi be the cost share of player i∈N,which is to be computed,so that the vectorπ=(π1,...,π|N|)denotes a cost allocation.Furthermore,let c:2N→I R be the characteristic function of the game which assigns a cost to each coalition S⊆N which is the outcome for the coalition S,if the players in S cooperate without the players in N\S.To be efficient,one must haveπi=c(N).i∈NThe cost allocationπis called an imputation,ifπi≤c({i})for all i.This may be considered a desirable property of the cost allocation,because otherwise a single player has lower cost when acting alone and cooperating is not rational.Similarly, a coalition S⊂N,S=∅,of the players will cooperate with the rest,ifi∈Sπi≤c(S)(1) holds.An imputation that fulfills the latter condition for all possible coalitions S⊂N, S=∅,is called a core element,soC(N,c)={π∈I R|N||i∈Nπi=c(N)andi∈Sπi≤c(S)for all S⊂N,S=∅}(2)is the core.The concept of the core is credited to Gillies(1959).Note that valuesπi<0are allowed,butπi≥0automatically holds for core allocations, if the characteristic function c is monotone,i.e.c(S1)≤c(S2)for all S1⊆S2⊆N:πi=c(N)−j∈N\{i}πj≥c(N)−c(N\{i})≥0.A cooperative game is said to be subadditive if for any pair of disjoint player sets S1,S2⊆N(with S1,S2=∅and S1∩S2=∅),we havec(S1)+c(S2)≥c(S1∪S2).Clearly,there exists an incentive to cooperate in subadditive games with transferable utilities.While the definition of the core is well established,the question of how to determine a core element is open in many situations.It is well known that for concave games, i.e.games wherec(S1∪{i})−c(S1)≥c(S2∪{i})−c(S2)holds for every i∈N and S1⊂S2⊆N\{i},the core equals the convex hull of the game’s marginal vectors(see Ichiishi,1981,and Shapley,1971)and therefore computing a marginal vector yields a core element.Unfortunately,many games are not concave. Even worse,for many games it is not clear whether or not the core is empty.As a result, many contributions to cooperative games prove the non–emptiness of the core for specificgames(often without computing a core element explicitly,but by proving that the game is balanced—the Bondareva–Shapley theorem,see Bondareva,1963,and Shapley,1967), or prove the property of concavity for a specific game(or show that the particular game is not concave by giving a counterexample).If core elements are explicitly computed tailor–made procedures are constructed—approaches that are very specific to the underlying problem and cannot be generalized.We refer to the survey given by Borm et al.(2001) for examples in this regard.For papers with structural or general algorithmic results we refer to the following selection:•Complexity results:The problem of testing core membership and the problem of proving non–emptiness of the core are N P–complete in general(see e.g.Faigle et al.,1997,Fang et al., 2002,and Goemans and Skutella,2004).•Linear programming and the core:Owen(1975)deals with linear production games and shows how to obtain a point in the core by solving a linear program which is an important contribution,because using the dual variables of an LP formulation of a problem for defining a core element can be successful in other applications as well(see e.g.Chen and Zhang, 2006a).A generalized linear production model is studied by Granot(1986).Deng et al.(1999)derived importantfindings for combinatorial optimization games based on the central insight that the core is not empty for a particular class of problems, if and only if an associated linear program has an integral optimal solution.Several applications to games on graphs are presented.•Specific applications:Derks and Kuipers(1997)present an O(n2)algorithm to compute a core element in routing games with n customers.Kuipers(1993)derives several results for in-formation graph games(a subclass of minimum cost spanning tree games):with n players e.g.the core can be described by at most2n−1linear constraints.For transportation games,S´a nchez–Soriano(2006)shows that every core element isa particular pairwise distribution.For assignment games,Sotomayor(2003)re-veals that a unitary core has more than one optimal matching.Borm et al.(2001) review operations research games including games related to connection problems (fixed tree,spanning tree),routing problems(chinese postman,travelling salesman),scheduling problems(sequencing,permutation,assignment),production problems (linear production,networkflow),and inventory problems(see Section3).•Core approximations and core–related concepts:Kamiya and Talman(1991)propose an algorithm to compute an approximating core element for balanced games without side payments by subdividing an appropriate simplex into smaller simplices.Maschler et al.(1979)discuss geometric properties of the( –)core and related concepts such as the kernel and the nucleolus.The nu-cleolus is inside the core,if the core is not empty(Schmeidler,1969).Hallefjord et al.(1995)compute the nucleolus for linear programming games by means of row generation(an idea that we will use as well)and G¨o the–Lundgren et al.(1996)com-pute the nucleolus of a vehicle routing game by means of row generation where the subproblem is a hard–to–solve mixed–integer programming problem(see Chardaire, 2001,for a note on the latter paper).Faigle et al.(2001)review the contributions on computing the nucleolus and provide an algorithm by their own.•Core properties:A particular selection from the core,the core–center,is discussed by Gonz´a lez–D´ıaz and S´a nchez–Rodr´ıguez(2007).Van Velzen et al.(2002)show that if specific sets of marginal vectors are core elements,then the game is concave.Hamers et al.(2002) study assignment games to prove that the extreme points of the core are marginal vectors.N´u˜n ez and Rafels(1998)prove that the extreme points of the core have a certain property,the reduced game property.Solymosi(1999)proves necessary and sufficient conditions under which the core coincides with the bargaining set for subadditive games.•Game variants:Faigle(1989)derives core theorems for cooperative games with restricted coopera-tion.Bilbao et al.(2007)define the core for bicooperative games.Okamoto(2002) investigates properties of the core of a game on a convex geometry.Lehrer(2002) deals with a temporal aspect of games where at each stage a budget is distributed among the players and demonstrates that specific allocation processes converge to the core.Multiple scenario cooperative games are such where the cost of a coalition is valued in different scenarios.Hinojosa et al.(2005)extend the notions of core, least core,and nucleolus for such settings.The major contribution of our paper is the proposal of a general algorithm that can be applied to a broad class of cooperative games.Section2.1describes an algorithm to compute a core element.This procedure can be modified for variants of the core,namely the –core and the least core,which is discussed in Section2.2.Since a core element is not unique in general,Section2.3discusses fairness issues to select a specific core element. Section3applies this algorithm to a specific application,namely inventory games based on the Wagner–Whitin problem.In Section4a computational study proves that games with150players can indeed be attacked.Final conclusions are made in Section5.2Computing a Core Element2.1A Row Generation ProcedureFormally,the definition of the core(2)specifies a constraint satisfaction problem where the number of constraints is exponential with an order of magnitude equal to2|N|.To tackle such a problem we suggest to use a row generation procedure.The master problem of this procedure basically is a relaxed version of the constraint satisfaction problem given by the core definition(2).Let S be a set of coalitions for which the condition in the core definition should explicitly be stated.Mathematically,we solve the following linear program:Master problem MP(S):min v(3)subject toi∈N πi=c(N)(4)i∈Sπi−v≤c(S)S∈S(5)πi∈I R i∈N(6)v≥0(7) The problem of computing a core element directly corresponds to the model formu-lation MP(S),if we choose S=2N\{∅,N},i.e.if we take2|N|−2constraints of type (5)explicitly into account.Note that the optimum objective function value of model MP(S)indicates whether or not the core is empty.If the optimum solution of MP(S) yields v=0,then the problem has a non–empty core and the valuesπi in that opti-mum solution define a cost allocation which is in the core.On the other hand,if theoptimum solution gives v >0,then we know that the cooperative game instance under consideration has an empty core.It should be emphasized that the values c (S )in the model formulation (3)–(7)are given parameters which means that in advance we have to determine c (N )in (4)and the |S|values c (S )in (5),but this computational burden is not due to our procedure and it is inherent to the definition of the core which assumes that all values c (S )for S ⊆N ,S =∅,are known in advance.The iterative row generation procedure can be outlined as follows:1.Define a small initial set S ,e.g.S ={{1},...,{|N |}}.2.Solve the linear program MP (S )optimally.3.If v >0then stop.The game instance has an empty core.4.Otherwise,find a coalition S ∈S (S =∅)such thati ∈S πi >c (S ).An opti-mization subproblem SP (π)which searches for a coalition S that violates the core defining inequality (1)most (i ∈S πi −c (S )is maximized)can,for instance,bedefined.5.If no such coalition S can be found ( SP (π)has a non–positive optimum objective function value)then stop.The current values πi define a core allocation.6.Otherwise,update S =S ∪{S }.Return to Step 2.2.2 –Core and Least–Core ElementsThe proposed procedure computes an element of the core.Closely related to the core are the concepts of the –core and the least–core.We will now show that slight modifications of our procedure can handle these core variants as well.The –core was introduced by Shapley and Shubik (1966)and is defined asC (c )={π∈I R |N ||i ∈N πi =c (N )andi ∈S πi ≤c (S )+ for all S ⊂N,S =∅}where ∈I R is a given parameter.Apparently,the core is a special case,i.e.C 0(c )=C (c ).The –core can be interpreted as follows:If founding a coalition S ⊂N and quitting the grand coalition incurs a cost >0,the grand coalition is stable even if the coalition S receives a cost share larger than c (S )as long as i ∈S πi ≤c (S )+ holds.If for founding acoalition S ⊂N and quitting the grand coalition a reward − >0is offered (from a third party),the grand coalition is stable as long asi ∈Sπi ≤c (S )−(− )is fulfilled.Notethat this interpretation is not meant to imply that the –core concept is senseful only if the grand coalition is given as a starting state.As stated already,the core of a cooperative game might be empty.But it should be clear that for a sufficiently large value the –core of the very same game is not empty. On the other hand,if the core of a game is not empty,then the –core lies within the core for ≤0,i.e.C (c)⊆C(c).Maschler et al.(1979)have formally defined the least–core C L(c)as being the –corewith smallest possible ∈I R such that C (c)is not empty,i.e.C L(c)=∈I R:C (c)=∅C (c).Hence,Maschler et al.(1979)describe the least–core as centrally located within the core, if the core is not empty( ≤0),and as a means to reveal the position of the“latent”core,if the core is empty( >0).Our procedure can be adapted tofind an element of the –core as follows:Replace(5) in the master problem byi∈Sπi−v≤c(S)+ S∈Sand replace the subproblem’s objective bymaxi∈Sπi−c(S )−To compute an element in the least–core,we have to do the two substitutions that were just described for the –core.Furthermore,we delete the variable v from the modelso that the constraints(5)are of the formi∈Sπi≤c(S)+ .In addition, must bea real–valued decision variable(and not a parameter in the master problem)and the objective function of the master problem must bemininstead of(3).The value to be used in the subproblem equals the objective function value of the most recent master problem.In the following,we will confine our discussion to the core and we will not treat its related concepts explicitly.2.3FairnessIn this subsection we assume that the game has a non–empty core which can be checked by running the algorithm introduced so far.In general,however,the core does not consistof a single element only.So we may want tofind a core cost allocation with a certain characteristic.While every core element is stable in the sense that no coalition has an incentive to leave the grand coalition,an arbitrary core element may not be considered as being fair.This aspect can be taken into account by using a slightly different master problem formulation.Two variants shall be suggested here.Variant I:The absolute cost shares should deviate as little as possible among the players:Master problem MP I(S):minΠ−Π≥≤Π,Π∈|N||N|≤c(N)fo|N|=|N|c(NVariant II:The percentage cost savings should deviate as little as possible among the players:Master problem MP II(S):minΠ−Π≥≤Π,Π∈c({j})c(Nc({i})≤c(N)foc({j})c(Nc({j})c(N3An Application:Inventory Games3.1Cooperative ProcurementDue to the growing number of supply chain management success stories companies are more and more involved nowadays.Business units are forced to think in terms of complex supply chain networks rather than in terms of isolated decision making.Arshinder and Deshmukh(2008)discuss coordination issues in supply chains.Figuring out if and how cooperation with others can improve own performance is an established paradigm today. Game theory methods are adequate to investigate such situations.We refer to Leng and Parlar(2005),Meca and Timmer(2008),and Nagarajan and So˘s i´c(2006)for a recent survey.In this section we will study cooperation in placing orders.Tella and Virolainen (2005)examine motives behind joint ordering.Not only private companies consider joint ordering as an important topic,but public bodies usually join cooperative procurement programs to form a purchasing alliance and to benefit from economies of scale.Note that we use the terms procurement problem,ordering problem,and lot sizing problem as synonyms in this paper.•EOQ/EPQ–related games:Meca et al.(2004)term the situation of cooperative procurement an inventory game.They use the well–known economic order quantity(EOQ)model as a basis.The advantage of their approach is that an analytical treatment of the problem is possible and that for all results a closed form solution(a formula)can be derived.The results obtained have been extended for a game based on the economic production quantity(EPQ)model with shortages by Meca et al.(2003).This work has been extended even further by Meca(2007)for generalized holding costs.Temporary price discounts are included by Meca et al.(2007).Dror and Hartman(2007)discuss a multi–product extension of the EOQ–based game.•Newsvendor–related games:Parlar(1988)was probably thefirst who considered games based on random de-mand inventory problems.Hartman et al.(2000)and Slikker et al.(2001)use the newsvendor inventory model as a basis for a cooperative game that is called inventory centralization game in the literature.Hartman et al.(2000)reveal as-sumptions under which newsvendor based games do not have an empty core.They also provide conditions which are equivalent to the condition of the Bondareva–Shapley theorem under the assumption of independent and identically distributed(iid)demands.M¨u ller et al.(2002)prove that the core of the newsvendor game is nonempty regardless of the joint distribution of the random demands.Hartman and Dror(2003)present a greedy optimization procedure to compute a solution that minimizes the cost of centralization.Conditions on the holding and penalty costs that ensure subadditivity of the game are derived by Hartman and Dror(2005).A dynamic version of the newsvendor game is presented by Dror et al.(2008).The possibility of transshipment between the newsvendors is added to the problem by Slikker et al.(2005).¨Ozen et al.(2007b)prove the non–emptiness of the core ina newsvendor setting where goods are delivered to warehouses before they reachthe retailers.Demands are realized when the goods reach the warehouse and order quantities can be reallocated before shipping from the warehouses to the retailers takes place.Chen and Zhang(2006b)show that determining whether an allocation is in the core of a newsvendor game is N P–hard even in very simple settings.Price–dependent demand and quantity discounts are introduced by Chen(2007)(see also Guardiola et al.,2007c,for quantity discounts in a different setting)and demand updates are discussed by¨Ozen et al.(2007a).•Wagner–Whitin–related games:Inventory games with discrete dynamic demand over multiple periods have been introduced by Guardiola et al.(2007a)and are called production inventory games.The costs taken into account are holding costs,backlogging costs,and production costs.It is shown that the core is not empty and a point in the core can be computed in polynomial time.An axiomatic foundation for the point computed is provided by Guardiola et al.(2007b).Setup costs are added by Guardiola et al.(2006)who coined the name setup inventory games.Chen and Zhang(2006a)compute a core element of a setup inventory game in polynomial time by utilizing linear program-ming duality(an approach which heavily relies on a specific model formulation while our approach is more general and independent from the mathematical properties ofa specific model formulation).Another paper on setup inventory games is the oneby van den Heuvel et al.(2007a)where the well–established Wagner–Whitin model (Wagner and Whitin,1958)is used as a starting point.So do we:A single decision maker has to make order decisions for a single item.Given a planning horizon of T time periods,a demand d t has to be met without backlogging and without shortages in every period.In order to meet the demand in period t one may place anorder in t or before.If the order is placed before,the ordered items must be stored in inventory.If a fixed cost s t is incurred whenever an order is placed in period t and a unit holding cost h t is charged for every item on stock at the end of period t ,then we face the classical trade–offbetween saving fixed costs versus saving holding costs —a lot sizing problem occurs.In addition to that a unit ordering cost p t is incurred for each item being ordered.The decision to be made is q t ,the quantity to be ordered in period t .Depending on the order quantities and the demand we have I t units of the item on stock at the end of a period t .This problem can be couched as a mixed–integer programming problem using the following notation:Parameters:Tthe number of periods I 0the quantity on stock at the beginning of period 1,w.l.o.g.I 0=0d t the demand in period t s t the fixed cost for placing an order in period t h t the holding cost coefficient for having one unit on stock at the end of period t p t the unit cost of ordering an item in period t M a big number,e.g.M = t d tDecision variables:q t the quantity to be ordered in period t I t the number of items on stock at the end of period t x t =1,if an order is placed in period t (0,otherwise)Given this notation the problem of finding order quantities which minimize cost can be stated as follows:min Tt =1(s t x t +h t I t +p t q t )(8)subject toI t =I t −1+q t −d tt =1,...,T (9)q t ≤Mx tt =1,...,T (10)q t ,I t ≥0t =1,...,T (11)x t ∈{0,1}t =1,...,T (12)The objective(8)is to minimize the sum offixed and quantity dependent ordering costs and holding costs.The inventory balance(9)states that at the end of a period we have on stock what was there at the beginning of the period plus what was ordered in that period minus period demand.If the order quantity is positive in period t then the indicator variable x t must be set to one as stated by(10).The domain of the decision variables is specified in(11)and(12).Note that due to I t≥0all demand must be fulfilled right in time.Although it is well–known that the Wagner–Whitin problem(8)–(12)can be solved very efficiently(see Federgruen,1991,Wagelmans,1992,and Aggarwal and Park,1993), the problem remains to be an optimization problem where no closed formula can be provided to specify the result.The situation described up to here assumes a single player.Now assume that multiple players consider to cooperate and let the set of all players be N with|N|≥2.A cooper-ation here means that these players decide to place orders together.More formally this means that each player i∈N faces a demand d it to be met in period t.If the players from the set N cooperate,they face a joint demandd t(N)=d it.i∈NFollowing van den Heuvel et al.(2007a)the problem to be solved for this group of players is the following:Tc(N)=min(s t x t+h t I t+p t q t)(13) t=1subject toI t=I t−1+q t−d t(N)t=1,...,T(14)q t≤Mx t t=1,...,T(15)q t,I t≥0t=1,...,T(16)x t∈{0,1}t=1,...,T(17) where c(N)is the total cost for ordering jointly.Note that c(S)≥0,for all S⊆N,and c(∅)=0by construction.The property of subadditivity holds which is a consequence of the totally balanced character of this type of games(Guardiola et al.,2006).Hence,the defined cooperative procurement game gives a reason to the players in the set N to form the grand coalition. This,however,is true only if the characteristic function c measures a transferable utility(TU).Since we consider cost(money)here,this is the case and the procurement game obviously is a TU game.The characteristic function c is monotone,i.e.c(S1)≤c(S2)for all S1⊆S2⊆N,because of d t(S1)≤d t(S2).Van den Heuvel et al.(2007a)prove that the cooperative game(N,c),which is based on model(13)–(17),has a non–empty core.However,they provide no way to compute a core element for the general case.Nevertheless,van den Heuvel et al.(2007a)show that this game is not concave in general.For two special cases they can prove concavity, namely the two–period case T=2and the case where all players face equal demand, i.e.d it=d jt for all i,j∈N and t=1,...,T.Our procedure can be applied now(a numerical example will be given in the subsequent subsection)where the subproblemSP(π)is defined to be the following:SubproblemSP(π):max−obj+i∈Nπi z i(18) subject toI t=I t−1+q t−i∈Nd it z i t=1,...,T(19)q t≤Mx t t=1,...,T(20)obj=Tt=1(s t x t+h t I t+p t q t)(21) q t,I t≥0t=1,...,T(22)x t∈{0,1}t=1,...,T(23)z i∈{0,1}i∈N(24)obj≥0(25) Note that a coalition S to be considered in the master problem is found,if the optimum objective function value of the subproblem is positive.S is defined by the values of the z i variables(z i=1indicates i∈S )and c(S )=obj,i.e.obj denotes the objective function value of the Wagner–Whitin problem which corresponds to the coalition S .The symbols πi denote parameter values.These values are computed by solving the master problem (πi was a decision variable in the master problem).Van den Heuvel et al.(2007b)prove that the subproblem in N P–complete.3.2A Numerical ExampleA small example shall now be given to illustrate the working principle of our procedure. We use here Example5from van den Heuvel et al.(2007a).(Note that this example contains a small mistake in the original paper:misprinted parameter values.Van den Heuvel sent to us the corrected values upon request.)This example consists of|N|=3 players and T=6periods of time.The parameter values are defined to be as given in Table1,I0=0.t123456d1551492011∅c(S)0π2≤5113≤(0,1393,0)π2+π3≤869(0,0,1393)(1393,0,0)π1≤644π1+π3≤1004π1+π2≤1029Figure 1:The Core {(π1,π2,π3)}of the Exampleπ2−v ≤511π3−v ≤483π1,π2,π3∈I Rv ≥0The optimum solution is v =0andπ=(644,511,238).Now we solve the subproblem.The result is z 1=1,z 2=1,and z 3=0which is true,because π1+π2=1155>1029=c ({1,2}).Iteration 2:Solve MP ({{1},{2},{3},{1,2}})optimally which means to solve the master problem from iteration 1with the additional constraintπ1+π2−v ≤1029.The optimum solution is v =0andπ=(518,511,364).The subproblem is called which gives the result z 1=0,z 2=1,and z 3=1,because π2+π3=875>869=c ({2,3}).。