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]

k4even.mos

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

   file k4even.mos
   ```````````````
   Placing a given number of chips on a 4x4 grid 
   such that every row and every column contains
   an even number of chips.
   - Enumerating multiple solutions -
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. June 2011
*******************************************************!)

model "K-4 Even"
 uses "mmxprs"

 declarations
  POS = 1..4                          ! Positions in a row/column
  NCHIP = 10                          ! Number of chips
    
  place: array(POS,POS) of mpvar      ! 1 if chip at the position, 0 otherwise
  row, column: array(POS) of mpvar    ! Chips per row/column divided by 2
 end-declarations

! Total number of chips
 sum(r,c in POS) place(r,c) = NCHIP

! Even number of chips in all rows and columns
 forall(r in POS) sum(c in POS) place(r,c) = 2*row(r)
 forall(c in POS) sum(r in POS) place(r,c) = 2*column(c)
 
 forall(r,c in POS) place(r,c) is_binary
 forall(r in POS) do
  row(r) is_integer; row(r) <= 2
  column(r) is_integer; column(r) <= 2
 end-do   
 
! Solve the problem: no objective
 setparam("XPRS_enummaxsol", 100)   ! Max. number of solutions to be saved
 minimize(XPRS_ENUM,0)

! Solution printing
 forall(i in 1..getparam("XPRS_enumsols")) do
  selectsol(i)                      ! Select a solution from the pool
  writeln("Solution ", i)
  forall(r in POS) do
   forall(c in POS) write( if(getsol(place(r,c))>0, "X ", ". ") )
   writeln
  end-do
 end-do 
 
end-model