FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious example

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 nameDifficulty
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]




k3congress_ka.mos

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

   file k3congress_ka.mos
   ``````````````````````
   Congress puzzle
   
   At an international congress taking place on 7-11 August
   five researchers of different nationality are giving talks,
   each on a different day. Find out the date and nationality
   for every researcher from the following information:
   a) Michael is not Japanese.
   b) Eric is French and he talks before the 10th.
   c) Arabinda talks on the 9th.
   d) The Chinese who is not Hitoshi gives his talk on the 8th, 
      before Michael.
   e) Hitoshi does his talk after the Indian and before the American.
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, March 2005
*******************************************************!)

model "K-3 Congress (CP)"
 uses "kalis"

 declarations
  DAYS = 7..11
  NAMES = {"Arabinda","Eric","Hitoshi","Michael","Zhicheng"}
  NAT = {"Japanese","French","Chinese","American","Indian"}
    
  talkp: array(NAMES) of cpvar         ! Choice of day for person p
  talkn: array(NAT) of cpvar           ! Choice of day for nationality n
 end-declarations

 forall(p in NAMES) setdomain(talkp(p), DAYS)
 forall(n in NAT) setdomain(talkn(n), DAYS)

! Every researcher on a different day
 all_different(talkp)
 
! Every nationality exactly once
 all_different(talkn)
 
! a: Michael is not Japanese
 talkp("Michael") <> talkn("Japanese")

! b: Eric is French and he talks before the 10th
 talkp("Eric") = talkn("French")
 talkp("Eric") <= 9

! c: Arabinda talks on the 9th
 talkp("Arabinda") = 9

! d: The Chinese who is not Hitoshi gives his talk on the 8th, before Michael
 talkp("Hitoshi") <> talkn("Chinese")
 talkn("Chinese") = 8
 talkp("Michael") >= 9

! e: Hitoshi does his talk after the Indian and before the American
 talkp("Hitoshi") >= talkn("Indian") + 1
 talkp("Hitoshi") <= talkn("American") - 1
 
 ! Solving and solution printing
 if cp_find_next_sol then
  forall(p in NAMES) do
   write(p," (") 
   day:= getub(talkp(p))
   forall(n in NAT) write( if(getub(talkn(n))=day, n, "") )
   writeln(") : ", day)
  end-do
 else
  writeln("Problem is infeasible")
 end-if

end-model
Back to examples browserPrevious example
© Copyright 2024 Fair Isaac Corporation.