## Wednesday, September 4, 2024

### Multiple Solutions in Minimum Spanning Tree example

In [1], I discussed some LP and MIP formulations for the Minimum Spanning Tree (MST) problem.

 Minimum Spanning Tree visualized through Google Maps

Here, I focus on two formulations: a multicommodity network approach (this can be solved as a large LP) and a MIP formulation based on techniques we know from the Traveling Salesman Problem (TSP). The main issue I want to discuss is the presence of multiple optimal solutions.

## Sunday, September 1, 2024

### N-queens and solution pool

In [1], I described some chess-related problems. Here, I want to reproduce the $$n$$-queens problem. The single solution problem, placing as many queens on the chess board as possible so they don't attack each other, is pretty standard. I want to focus on the more complex question: How many different ways can we place those queens? In other words: what are all the optimal solutions? We can do this by adding a no-good constraint that forbids the previously found solution. However, as this problem has more than a handful of different solutions, I want to use the Cplex solution pool.

### Single Solution Model

We define the decision variables as: $\color{darkred}x_{i,j} = \begin{cases} 1 & \text{if we place a queen on the square (i,j)} \\ 0 & \text{otherwise}\end{cases}$

 Chess Board