FICO Xpress Optimization Examples Repository: Puzzles and pastimes from the book `Programmation Lineaire'

FICO Xpress Optimization Examples Repository

Puzzles and pastimes from the book `Programmation Lineaire'

Description

The following models implement solutions to the puzzles published in the book `Programmation Lineaire' by C. Gueret, C. Prins, and M. Sevaux (Eyrolles 2000, in French). Each problem is implemented as a MIP and as a CP model.

*Problem name*		*Difficulty*
K‑1	Playing Mastermind	**
K‑2	Marathon puzzle	*
K‑3	Congress puzzle	*
K‑4	Placing chips	*
K‑5	Nephew puzzle	**
K‑6	N-queens problem	*

These models show how to formulate different logical constraints using binary variables (MIP models) or logical constraint relations and global constraints (CP models).

bookpuzzle.zip

[download all files]

Source Files

By clicking on a file name, a preview is opened at the bottom of this page.

k1masterm_ka.mos	[download]
k2marath_ka.mos	[download]
k3congress_ka.mos	[download]
k4even_ka.mos	[download]
k5nephew_ka.mos	[download]
k6queen_ka.mos	[download]
k6queen_ka_graph.mos	[download]
k1masterm.mos	[download]
k2marath.mos	[download]
k3congress.mos	[download]
k4even.mos	[download]
k5nephew.mos	[download]
k6queens.mos	[download]

k1masterm_ka.mos

(!******************************************************
   Mosel Example Problems
   ======================

   file k1masterm_ka.mos
   `````````````````````
   Playing Mastermind

   Given information:
   Round  Pos.1   Pos.2   Pos.3   Pos.4   Judgement
    1     red     yellow  white   green   1 color well positioned, 
                                          1 color on wrong position  
    2     blue    green   white   blue    1 color well positioned
    3     yellow  black   white   black   1 color well positioned, 
                                          1 color on wrong position
    4     blue    yellow  red     black   all colors on wrong position
       
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, March 2005
*******************************************************!)

model "K-1 Mastermind (CP)"
 uses "kalis"

 declarations
  POS = 1..4                          ! Positions in a row
  COLORS = 1..6                       ! 1: White, 2: Blue, 3: Yellow,
                                      ! 4: Black, 5: Red, 6: Green
  place: array(POS) of cpvar          ! Color of position
  use: array(COLORS) of cpvar         ! Number of occurences of a color
 end-declarations
 
! Creation of variables
 forall(p in POS) do 
  1 <= place(p); place(p) <= 6; end-do
 forall(c in COLORS) do 
  0 <= use(c); use(c) <= 4; end-do
 
! Relation between placement variables and choice indicators
 forall(c in COLORS) use(c) = occurrence(c, place)
 sum(c in COLORS) use(c) = 4

! Round 1: 1 color well positioned, 1 color on wrong position
 place(1)=5 or place(2)=3 or place(3)=1 or place(4)=6
 use(5) + use(3) + use(1) + use(6) = 2

 writeln("Round 1: ", place, use) 
 
! Round 2: 1 color well positioned
 place(1)=2 or place(2)=6 or place(3)=1 or place(4)=2
 use(2) + use(6) + use(1) = 1

 writeln("Round 2: ", place, use) 

! Round 3: 1 color well positioned, 1 color on wrong position
 place(1)=3 or place(2)=4 or place(3)=1 or place(4)=4
 use(3) + use(4) + use(1) = 2

 writeln("Round 3: ", place, use) 
 
! Round 4: 4 colors on wrong position
 place(1)<>2; place(2)<>3; place(3)<>5; place(4)<>4
 forall(p in POS) do
  2 <= place(p); place(p) <= 5
 end-do
 use(2)=1; use(3)=1; use(5)=1; use(4)=1 
 
 writeln("Round 4: ", place, use) 



! Branching strategy
 cp_set_branching(assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX, place))

! Solve the problem
 if not cp_find_next_sol then
  writeln("Problem is infeasible")
  exit(1)
 end-if

! Solution printing
 declarations
  COLORNAMES: array(COLORS) of string
 end-declarations
 
 COLORNAMES:: ["White","Blue","Yellow","Black","Red","Green"]
 
 forall(p in POS)
  writeln("Position ", p, ": ", COLORNAMES(getsol(place(p))) )
  
end-model