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]

k6queens.mos

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

   file k6queens.mos
   `````````````````
   Placing N queens on an NxN chess board such that 
   they do not attack each other.
   - Enumerating multiple solutions -
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. June 2011
*******************************************************!)

model "K-6 Queens"
 uses "mmxprs"

 declarations
  NQ = 8                              ! Number of rows and columns
  POS = 1..NQ
    
  queen: array(POS,POS) of mpvar      ! 1 if queen at a position, 0 otherwise
 end-declarations

! Objective: total number of queens
 Total:= sum(r,c in POS) queen(r,c)

! Single queen per row and column
 forall(r in POS) sum(c in POS) queen(r,c) = 1
 forall(c in POS) sum(r in POS) queen(r,c) = 1

! Diagonals
 forall(c in POS) sum(r in c..NQ) queen(r-c+1,r) <= 1
 forall(r in 2..NQ) sum(c in r..NQ) queen(c,c-r+1) <= 1
 forall(c in POS) sum(r in 1..c) queen(r,c-r+1) <= 1
 forall(r in 2..NQ) sum(c in r..NQ) queen(c,NQ-c+r) <= 1

 forall(r,c in POS) queen(r,c) is_binary
 
! Solve the problem
 setparam("XPRS_enummaxsol", 100)   ! Max. number of solutions to be saved
 minimize(XPRS_ENUM,Total)

! Solution printing
 forall(i in 1..getparam("XPRS_enumsols")) do
  selectsol(i)                      ! Select a solution from the pool
  writeln("Solution ", i, ". Total number of queens: ", getobjval)
  forall(r in POS) do
   forall(c in POS) write( if(getsol(queen(r,c))>0, "Q ", ". ") )
   writeln
  end-do
 end-do 

end-model