2.6.1 A non-transitive relation (dice)

Run LPL Code  ,  PDF Document

Problem

In the dice problem a set of three dice has to be designed by assigning an integer number to each face such that on average dice 1 beats dice 2, dice 2 beats dice 3 and dice 3 beats dice 1. The goal is to maximize the number of total wins on average. The dice problem has many solutions. The problem is from Robert A Bosch, Monochromatic Squares, Optima, MP Society Newsletter, Vol 71, March 2004, page 6-7. A related problem is also implemented in monochrom.

Modeling Steps

Let f,fp Faces = {1,, 6} be the faces on a dices and let d Dices = {1,, 3} be the set of dices. The lowest face value is flo = 1, and the highest is fup = |Dice|⋅|Faces|. The variable Obj is the number of wins.

yi,f,fp is defined as follows: if face f of dice i wins (value 1) or loses (value 0) against face fp of dice i + 1 (circular).

  1. Count the wins of all dices:

    ∑
    yi,f,fp = Obj
f,fp
  2. The second constraint is the definition of yi,f,fp, that is, face f of dice i wins (value 1) or loses (value 0) against face fp of dice i + 1:

    xi,f + (fup -  flo)(1 - yi,f,fp) ≥ xif(i<|Dices|,i+1,1),fp + 1  forall i ∈ Dices, f,fp ∈ F aces
  3. All faces on a dice must have different numbers:

    x[i,f - 1] + 1 <= x[i,f]   forall i ∈ Dices, f ∈ F aces - {face1}
  4. We want to maximize the number of wins:

         ∑
max      y
          i,f,fp
      f,fp

LPL code (run dice)

model dice "A non-transitive relation"; 
  set 
    Faces,f,fp:=[1..6] "Faces on a dice"; 
    Dices,i := [1..3]  "Number of dices"; 
  parameter 
    flo := 1     "Lowest face value"; 
    fup := #i*#f "Highest face value"; 
 
  variable 
    Obj               "Number of wins"; 
    x{i,f} [flo..fup] "Face value of dice"; 
    binary y{i,f,fp}  "=1, if f beats fp (MatchOutcome)"; 
 
  constraint 
    Wins{i}: sum{f,fp} y[i,f,fp] = Obj "Count the wins"; 
    Fval{i,f,fp}: x[i,f] + (fup-flo)*(1-y[i,f,fp]) 
      >= x[if(i<#i,i+1,1),fp] + 1     "non-trans. relation"; 
    Fa{i,f|f>1}: x[i,f-1]+1 <= x[i,f] "diff face values"; 
    Fix: x['dice1','face1'] = flo     "fix one value"; 
  maximize N: Obj; 
end

AIMMS code (download dice.ams)

Model Dice_Model { 
    Comment: { 
        "Finding multiple solutions ..." 
    } 
    DeclarationSection Declaration_Model { 
        Set Faces { 
            Text: "Faces on a dice"; 
            Index: f, fp; 
            InitialData: data { face1 .. face6 }; 
        } 
        Set Dice { 
            Index: i; 
            InitialData: data { dice1 .. dice3 }; 
        } 
        Parameter LowestFaceValue { 
            Text: "Lowest face value"; 
            InitialData: 1; 
        } 
        Parameter HighestFaceValue { 
            Text: "Highest face value"; 
        } 
        Variable Obj { 
            Comment: "Number of wins."; 
        } 
        Variable FaceValue { 
            IndexDomain: (i,f); 
            Range: binary; 
            Comment: "Face value of dice."; 
        } 
        Variable MatchOutcome { 
            IndexDomain: (i,f,fp); 
            Range: binary; 
            Comment: { 
                "Binary variable indicating ..." 
            } 
        }

... continuing AIMMS code ...

 
        Constraint WinsConstraint { 
            IndexDomain: i; 
            Definition: Obj = sum( (f,fp), MatchOutcome(i,f,fp) ); 
            Comment: "Count the wins of all dice."; 
        } 
        Constraint MatchOutcomeConstraint { 
            IndexDomain: (i,f,fp); 
            Definition: FaceValue(i,f) + (HighestFaceValue-LowestFaceValue)*(1-MatchOutcome(i,f,fp)) >= FaceValue(i++1,fp) + 1; 
            Comment: { 
                "Constraint that determines ..." 
            } 
        } 
        Constraint FaceValuesConstraint { 
            IndexDomain: (i,f) | (f-1) in faces; 
            Definition: FaceValue(i,f-1) + 1 <= FaceValue(i,f); 
            Comment: "Constraint to enforce ..."; 
        } 
        MathematicalProgram DiceMP { 
            Objective: Obj; 
            Direction: maximize; 
            Constraints: AllConstraints; 
            Variables: AllVariables; 
            Type: MIP; 
        } 
    } 
    Procedure MainInitialization { 
        Body: { 
           HighestFaceValue := card(Dice) * card(faces); 
 
           FaceValue.lower(i,f) := LowestFaceValue; 
           FaceValue.upper(i,f) := HighestFaceValue; 
 
           FaceValue.lower('dice1','face1') := LowestFaceValue; 
           FaceValue.upper('dice1','face1') := LowestFaceValue; 
           FaceValue.level('dice1','face1') := LowestFaceValue; 
 
           SolutionMethod := 'normal'; 
        } 
    } 
    Procedure MainExecution { 
        Body: { 
            empty Objs, FaceValues; 
 
            ! Optimal objective value: 21. 
            solve DiceMP; 
 
            Objs(1) := Obj; 
            FaceValues(i,f,1) := FaceValue(i,f); 
        } 
        Comment: { 
            "Normal solve; returns one solution." 
        } 
    } 
    Procedure MainTermination { 
        Body: { 
            return 1; 
        } 
    } 
}