|
|
| |
Solving puzzles and pastimes with Mosel
The examples in this directory implement various puzzles and pastimes as MIP or Constraint Programming (CP) models. The MIP
models are solved with Xpress Optimizer; the CP models (files named *_ka.mos) can only be run if Xpress Kalis has been installed.
|
| Sudoku (CP model): Using 'all_different', enumerating all feasible solutions
|
| |
|
| Type: |
Assignment |
| Rating: |
2 (easy-medium) |
| Description: |
Playing Sudoku: fill in the 9x9 grid so that every row, every column and every 3x3 box contains the numbers 1-9.
- The model sudoku_ka.mos solves a given Sudoku grid by Constraint Programming.
|
| File(s): |
sudoku2_ka.mos |
| Data file(s): |
sudokug290705.dat, sudokut260105.dat |
|
|
| Futoshiki (CP and MIP models): Using 'all_different', formatted solution printout
|
| |
|
| Type: |
Assignment |
| Rating: |
2 (easy-medium) |
| Description: |
Playing Futoshiki: fill in the grid so that every row and column contains the numbers 1-5. The `greater than' of `less than'
signs indicate where a number is larger or smaller than its neighbor.
- The models futo.mos and futo_ka.mos solve a given Futoshiki grid with MIP and CP respectively.
|
| File(s): |
futo.mos, futo_ka.mos |
| Data file(s): |
futo1.dat, futo2.dat |
|
|
| Fantasy OR: Sangraal (CP and MIP models): Formulation of a scheduling problem with MIP and CP
|
| |
|
| Type: |
Scheduling |
| Rating: |
3 (intermediate) |
| Description: |
The Sangraal problem is an example of a mathematical problem
embedded in a computer fantasy game. The description of the problem and the mathematical model introduced below draw on
a publication by M.Chlond: M.J. Chlond, Fantasy OR,
INFORMS Transactions on Education, Vol. 4, No. 3, 2004.
http://ite.pubs.informs.org/Vol4No3/Chlond/
When the Sangraal (Holy Grail) is almost won the hero arrives at a castle where he finds 8 imprisoned knights. He is facing
the task to bring the largest possible number of knights for the arrival of the Sangraal in twenty minutes' time. The time
required for freeing a knight depends on his state of binding. A freed knight then needs a given amount of time to wash and
recover himself physically. For every knight, the durations of freeing and preparing are given.
The problem of deciding in which order to free the knights is a standard scheduling
problem, or to be more precise the problem of sequencing a set of disjunctive tasks.
Typical objective functions in scheduling are to minimize the completion time of the last task (the so-called makespan)
or the average completion time of all tasks. The objective to maximize the number of knights who are ready by a given time
makes the problem slightly more challenging since we need to introduce
additional variables for counting the knights who are ready on time.
- The MIP model (sangraal.mos) defines binary decision variables x(k,j) indicating whether knight k is the j'th knight to be
freed. A formulation alternative uses indicator constraints (sangraalind.mos).
- The CP model (sangraal_ka.mos or sangraal2_ka.mos) uses the notion of `tasks' with fixed durations and variable start times.
These tasks need to be scheduled subject to precedence relations (freeing before preparing) and the disjunctive use of a resource
(the hero's time).
|
| File(s): |
sangraal.mos, sangraal_graph.mos, sangraalind.mos, sangraal_ka.mos, sangraal2_ka.mos |
|
|
| Fiveleaper (MIP model and graphics): Subtour elimination algorithm
|
| |
|
| Type: |
Traveling Salesman Problem |
| Rating: |
4 (medium-difficult) |
| Description: |
A fiveleaper travels over the chessboard by advancing in a single move either 5 squares in a straight line or three squares
in a particular direction and 4 in an orthogonal direction. That is, with every move it travels a Euclidean distance of five
squares.
The problem of finding fiveleaper's tours on a chessboard
is an instance of the Traveling Salesman Problem (TSP) and we adapt the subtour elimination algorithm described in the book
'Applications of optimization with Xpress-MP' (problem f5tour) for solving this problem.
You will find a description of this problem and a few other
model versions in the following publication:
M.J. Chlond, B. Daniel, S. Heipcke, Fiveleapers a-leaping,
INFORMS Transactions on Education, Vol. 4, No. 1, 2003.
http://ite.pubs.informs.org/Vol4No1/ChlondDanielHeipcke
The model version fiveleap_graph.mos displays a user graph within a webbrowser. The model fiveleap.mos simply prints out the
results and will work on any platform for which Mosel is available.
|
| File(s): |
fiveleap.mos, fiveleap_graph.mos |
|
|
| Puzzles and pastimes from the book `Programmation Lineaire': MIP and CP formulations for discrete feasibility problems
|
| |
|
| Type: |
Discrete puzzles |
| 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).
|
| File(s): |
k1masterm_ka.mos, k2marath_ka.mos, k3congress_ka.mos, k4even_ka.mos, k5nephew_ka.mos, k6queen_ka.mos, k6queen_ka_graph.mos |
|
|
|
|
|