CS4341 Project – 5 CSP solution

The goal of this project is to understand Constraint Satisfaction Problems (CSP) as well as to implement a program that solves a constraint satisfaction problem. You will need to understand Back-tracking, Forward Checking, and other various heuristics for this assignment.

Do in pairs or solo.

The following is an example of a bag-packing problem. Imagine a group of thieves broke into a store! There are N items of various weights in the store, and the thieves are carrying M bags (a bag for each thief) with each bag having a maximum capacity. Your task is to come up with a program that helps filling the bags under certain constraints. We will use the following notation for this project:

• Items (CSP variables)We have N items denoted by UPPER case letters (e.g. A, B, C, D, …). Each item has weight associated with it. All items must be assigned to a bag, and only one bag.
• Bags (Variables’ domains- the values)We will denote the M bags by lower case letters (e.g. p, q, r, s, t, …). Each bag has a capacity, namely how much weight it can hold. The items must be assigned to the bags such that the sum of their weights do not exceed the the maximum capacity, and the bags must be at least 90% full (Rounded down to the nearest int. A bag with a capacity of 100 must hold at least 90 kg, capacity 101 = at least 90, capacity 4 = at least 3, ect).
• ContraintsThe constraints are of the following sort:
  • Bag Fit-Limit (Number of items in each bag):
    • Any bag must contain at least x items but no more than y items. We assume that x and y are the same for all bags.
  • Unary constraints (involving one variable):
    • Assume that the thieves are picky, and they require certain items to be placed in certain bags. Hence a unary inclusive constraint specifies that a certain item can only be assigned to certain possible bags. For example, item A can only be assigned to bags p, q, r, or s.
    • On the other hand, they also require that certain items can’t be placed in some bags. In this case, a unary exclusive constraint specifies which bags an item must NOT be allocated to. For example: item B can be assigned to neither bag p nor bag q.
  • Binary constraints (involving two variables):
    • Equality: We have binary equality constraint to specify that two items must be placed in the same bag.
    • Inequality: On the other hand, we use binary inequality constraint to specify that two items must NOT be placed in the same bag.
    • Mutual Inclusive-ity: Two given items must be simultaneously assigned to a given pair of bags, if at least one of those items is in one of those bags. Mutual Inclusivity constraint ‘A B p q’  says that if item A gets placed into one of bags p or q, then item B must be placed into the other (and similarly if B is allocated first, then A must get into the other).  But if A is placed in any other bag, then B can be placed anywhere.

Your program (or a script accompanying your program) must accept a filename as a single command-line argument. For example, you might run your program by typing “java Project2 filename.txt” or “runProject2 testfile.txt”. The test file specified by the argument has a specific format:

• The file has eight sections.
• Each section starts with a line that begins with “#####”. This line may contain comment information, which your program must ignore. For example, one of the beginning markers may be: “##### — This section contains unary inclusion constraints.”
• Therefore, there will be 8 section-beginning lines.
• The eight sections are each described below:
  • names and weights of the items
    • The beginning of this section is signaled by a single line that begins with “#####”.
    • Items are named by a single upper case letter.
    • Remember that items are the “variables” in the constraint satisfaction problem.
    • Each line in this section contains the name of an item, followed by one space, followed by the weight in kilograms.
    • The weight of each item is a strictly positive integer
    • An example line would be “D 10”. This means that there exists an item D which weighs 10 Kg
  • names of the bags and their capacity
    • The beginning of this section is signaled by a single line that begins with “#####”.
    • Bags are named by a single lower case letter.
    • Remember that bags are the “domain of the variables” in the constraint satisfaction problem.
    • Each line in this section contains the name of a bag, followed by one space, followed by the capacity in kilograms.
    • An example line would be “p 70”. This means that there exists a bag w with capacity 70 Kg.
  • Fit limits (Number of items in each bag)
    • The beginning of this section is signaled by a single line that begins with “#####”.
    • This is a special constraint that is particular to the bag-packing constraint satisfaction problem.
    • The number of items that are assigned to any given bag must be within the lower and upper limits
    • These limits are given as positive integers in one line separated by spaces.
    • An example line would be “3 8”. This means that all bags fit between 3 and 8 items. (Inclusive range [3,8])
  • unary constraints
    • Unary constraints contain only one variable (item).
    • There are two kinds of unary constraints: inclusive and exclusive.
    • In order to make the constraints easier to parse, the two different kinds of unary constraints are separated.
      1. Inclusive unary constraints
         • The beginning of this section is signaled by a single line that begins with “#####”.
         • Inclusive unary constraints are specified by a variable (item), and a list of values (bags).
         • The inclusive unary constraint means that the variable must be assigned to one of the values.
         • An example line would be “A p q r s”. This means that the value assigned to item A must be either p or q or r or s.
      2. Exclusive unary constraints
         • # The beginning of this section is signaled by a single line that begins with “#####”.
         • # Exclusive unary constraints are also specified by a variable (item), and a list of values (bags).
         • # The exclusive unary constraints mean that the variable must not be assigned one of the values.
         • An example line would be “C u v w x”. This means that the value assigned to item C must be neither u nor v nor w nor x.
  • binary constraints
    • Binary constraints contain two variables (items).
    • There are three kinds of binary constraints: equal, not equal, and simultaneous.
      1. Equal binary constraints
         • The beginning of this section is signaled by a single line that begins with “#####”.
         • Equal binary constraints are specified by two variables (items).
         • The equal binary constraints mean that the two variables (items) must be assigned the same value (bag).
         • An example line would be “E F”. This means that the same value must be assigned to both E and F.
      2. Not equal binary constraints
         • The beginning of this section is signaled by a single line that begins with “#####”.
         • Not equal binary constraints are also specified by only two variables (items).
         • The not equal binary constraints mean that the two variables (items) must be assigned different values (bags).
         • An example line would be “G B”. This means that the G and B must not be assigned to the same value.
      3. Mutual Inclusive binary constraints
         • The beginning of this section is signaled by a single line that begins with “#####”.
         • Mutual inclusive binary constraints are specified by two variables (items) and a pair of values (two bags).
         • The mutual inclusive binary constraints mean that the pair of assignments must both be made if one of the assignments is made. For example, a line “A B x y” means x must be assigned to A if y is assigned to B, and vice versa (for each of the bag / item names).
         • The below mutual exclusion rules imply that Item A cannot be placed into Bag “a” because that would require that Item B be placed into two different bags (b & c).
           • A B a b
             A B a c

Several test files will be made available during the course of the project. Your program must work on all of them. One sample file is included below:

##### - variables (items and their weight)
A 30
B 30
C 30
D 30
E 40
F 35
H 45
##### - values (bags and their capacity)
x 70
y 90
z 80
##### - fitting limits (each bag must have 1 item and not more than 3 items
1 3
##### - unary inclusive (item B can go in bag z or y)
B z y
##### - unary exclusive (-first line below item A can not go in bag z)
A z
E y
##### - binary equals . (item C and B need to be in the same bag)
C B
##### - binary not equals (Item A and E need to go in different bags) 
A E
##### - mutual inclusive (If Item F is in either bag y of z than H must be in the other bag)
F H y z

• This file describes a bag-packing constraint satisfaction problem that has 7 items and 3 bags that fit 1 to 3 items.
• The unary constraints are that variable B must be assigned either value z or y; variable A must not be assigned value z; variable E must not be assigned value y.
• The binary constraints are that variable C must be assigned the same value as variable E; Variable A must not be assigned the same value as variable E;
• The mutual inclusive constraint: If F is assigned y, H must be assigned z
• As stated above, each input file has 8 sections, even if some of the sections are empty. (the section header is always given)
• ITEMS ARE CAPITAL LETTERS. BAGS ARE LOWERCASE LETTERS.