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]

k5nephew_ka.mos

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

   file k5nephew_ka.mos
   `````````````````
   Distributing wine barrels among nephews
   
   A farmer wishes to distribute his 45 wine barrels among
   his 5 nephews. 9 barrels are full, 9 filled to 3/4, 
   9 half-full, 9 filled to a quarter, and 9 are empty.
   Each nephew is to receive the same number of barrels
   and the same volume of wine. Furthermore, each nephew
   must receive at least one barrel of every type and 
   no two of the nephews must be allocated exactly the
   same number of barrels of every fill type. 

   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, March 2005, rev. Jan. 2018
*******************************************************!)

model "K-5 Nephew (CP)"
 uses "kalis"

 setparam("KALIS_DEFAULT_UB", 100000)

 declarations
  NN = 5; NT = 5
  NEPHEWS = 1..NN                     ! Nephews
  TYPES = 1..NT                       ! Contents types of wine barrels
  BARRELS = 45
    
  COEF: array(TYPES) of integer       ! Factors for "all_different" constraint
  FILL: array(TYPES) of integer       ! Fill level of barrels

  give: array(NEPHEWS,TYPES) of cpvar ! Barrels of type t for every nephew
  p: array(NEPHEWS) of cpvar          ! 'Pattern': value of the product
                                      !            c*give(n,t)
 end-declarations

 FILL:: [100, 75, 50, 25, 0]
 COEF:: [10000, 1000, 100, 10, 1]

! Bounds and names for variables
 forall(n in NEPHEWS, t in TYPES) do
  setname(give(n,t),"GIVE["+n+","+t+"]")
  1 <= give(n,t); give(n,t) <= NN
 end-do
 forall(t in TYPES) setname(p(t),"PRODUCT["+t+"]")  
 
! Barrels per nephew
 forall(n in NEPHEWS) sum(t in TYPES) give(n,t) = round(BARRELS/NN)
 forall(t in TYPES) sum(n in NEPHEWS) give(n,t) = round(BARRELS/NN)

! Equilibrated contents
 forall(n in NEPHEWS) 
   sum(t in TYPES) FILL(t)*give(n,t) = 
           round(BARRELS/NN * (sum(t in TYPES) FILL(t))/NT)
 
! Every nephew receives a different number of barrels of any given type
! (that is, a different pattern for every nephew)
 forall(n in NEPHEWS) do
  1 <= p(n); p(n) <= NN*COEF(1)
  sum(t in TYPES) COEF(t)*give(n,t) = p(n)
 end-do
 all_different(p)

! Branching strategy
 cp_set_branching(split_domain(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX, 
                               give, true, 2))

! Solve the problem
 if not(cp_find_next_sol) then
  writeln("Problem is infeasible")
  exit(1)
 end-if 
 
! Solution printing
 forall(n in NEPHEWS) do
  write(n,": ")
  forall(t in TYPES) write( give(n,t), " " )
  writeln
 end-do

end-model