Homework 2: CSG 270 Due: Jan. 24, 2007 UP* (Part 1 only) Due: Jan. 31, 2007 D, Update, Restart and Finale integrated into a partial solver ================================================================================= Starting with this homework, you are encouraged to work in teams of 2. If your schedule does not permit to meet with a partner, you are welcome to work by yourself. Working in team of 2 is a good opportunity to learn from each other. Make sure that you understand the material. Practice pair-programming using Eclipse. Implement a simple transition system for a partial solution to MAX-CSP In MAX-CSP we find an assignment that maximizes the fraction of satisfied constraints. Assignment = List(Literal). Literal : Pos | Neg common Variable. Variable = Ident. Pos = . Neg = "!". unsat(M,G) is the fraction of constraints in instance G that are unsatisfied under partial assignment M. State: M | F | N where M is a partial assignment, F is a CSP instance and N is the currently best assignment. Initial State: {} | F || N where N is the all 0 assignment (could be any other assignment). Transition rules: Unit-Propagation UP: M | F | N -> Mk | F | N if k is not in M and unsat(M !k,F) >= unsat(N,F) Decide: D: M | F | N -> Mk | F | N if k is not in M and v(k) occurs in some constraint in F. v(k) is the variable corresponding to the literal k. Update: M | F | N -> M | F | M if M is complete (all variables assigned) and unsat(M,F) < unsat(N,F). Restart: M | F | N -> {} | F | N Finale: (final transition) M | F | N -> M | F | N if unsat(N,F) = 0. Transition sequence: auxiliary sequence UPD = Restart (UP | D)* The sequence (UP | D)* must have the property that UP is given preference over D if UP is applicable. desired sequence (UPD Update)* Finale This transition system does not deal with the situation where unsat(M,F) >= unsat(N,F). That is the topic of future homeworks. The current system works well if the Decide rule makes always the "right" decisions. But if it makes a mistake. Part 1: The UP* rule ------------------------------------- An important step in a CSP solver is to determine the variables that are forced to a specific value because otherwsie we could not produce a better assignment. Given a CSP instance F and a currently best assignment N, find all forced variables including the ones that are forced by the forced variables. Example: We use the relation of rank 3 with number 3. The currently best assignment is "all 1". R3(a b c) c is variable 0 b is variable 1 a is variable 2 Here both a and b are forced to 0. When a variable is forced we reduce the instance by setting the variable the way it is forced. If we set a to 0 and b to 0 then R3(a b c) becomes satisfied. Write a program that takes as input a CSP instance F. It finds all forced variables, reduces the instance based on how the variables are forced. Then it finds again forced variables and repeats this loop until no variable is forced or all constraints are satisfied. Part 2: The Decide Rule D and the others ---------------------------------------- When no more variables are forced, we need to choose a variable to set next. Which variable to choose next is determined by a variable_ordering technique and how to set the chosen variable is determined by a value_ordering technique. Choose a simple variable_ordering technique, like "the first unassigned variable" and choose a simple value_ordering technique, like "flipping a fair coin". =========================== What do you learn from this exercise: 1. How to describe an implementation of a MAX-CSP solver at a high level of abstraction. I call this the Transition System Abstraction method, a useful software development method for many kinds of systems. 2. A deeper experience of the schema-binding method. Note how the schema determines the structure of your functions. 3. The "good separation of concerns" technique, a very general software development method. Notice how we separate the concern of defining the transitions from the concern how to sequence them. This leads to a more modular design. 4. Making options for generalization. While in this homework you implement a specific transition system for MAX-CSP, there is a later possibility to implement a transition system interpreter, that takes the description of a transition system for MAX-CSP and executes it. For this homework, you are encouraged to explicitly represent the transition system objects to have a permanent record of what the transition system did. =========================== What to turn in: Use blackboard for submitting your electronic homework. Electronic: Your program with test cases and output with instructions how to run it. Hardcopy (at beginning of class): A printout of your well documented program source code and three test cases with output.