I have done the Einstein's Riddle exercise with linear programming. I implemented this solutions in Gusek. How can i tell if there is more than one solution?
Einsten's riddle:
There are 5 houses in five different colors. In each house lives a person with a different nationality. These five owners drink a certain type of beverage, smoke a certain brand of cigar and keep a certain pet. No owners have the same pet, smoke the same brand of cigar or drink the same beverage.
Constaints:
the Brit lives in the red house
the Swede keeps dogs as pets
the Dane drinks tea
the green house is on the left of the white house
the green house's owner drinks coffee
the person who smokes Pall Mall rears birds
the owner of the yellow house smokes Dunhill
the man living in the center house drinks milk
the Norwegian lives in the first house
the man who smokes blends lives next to the one who keeps cats
the man who keeps horses lives next to the man who smokes Dunhill
the owner who smokes BlueMaster drinks beer
the German smokes Prince
the Norwegian lives next to the blue house
the man who smokes blend has a neighbor who drinks water
Can I tell which constraints are redundant?
Thank you for your help
Your decisions/solution will be in the form of binary or integer varibles.
If they are binary, add in a new constraint like the one below: (Y are all the binaries which were 1 and `Y are binaries which were 0.)
sum(Y) + sum(i-Y) != |Y|+|Y|
Keep repeating this till you get an infeasible model. This can be extended to the integer case too.
As for redundancy, you have to manually try removing them and see if the solution changes. However, in terms of reduncancy, you might have cases where constraint A and B are redundant OR constraint C is redundant. You could have multiple sets of potential redundant constraints depending on which you eliminate.