minizincoptimathsat

MiniZinc Geocode not printing all solutions to CSP with "all" solutions enabled


The Issue

With solve minimize I only get one solution, even though there are multiple optimal solutions. I have enabled printout of multiple solutions in the solver configurations. The other optimal solutions are found with solve satisfy, along with non-optimal solutions.

Possible causes

Could it be that the cardinality function card() ranks by enum value where size of two sets are equal? In other words that card(A, B) > card(B, C)? If so, do I have to switch the representation of my vertices?

The Program

I am creating a MiniZinc program for finding the minimum vertex cover of a given graph. The graph in this example is this:

Example graph

With Minimal Vertex Cover solutions being: [{A, B, C, E}, {A, B, E, F}, {A, C, D, E}, {B, C, D, E}, {B, C, D, F}, {B, D, E, F}]. My code only outputs {A, B, C, E}.

Data file:

VERTEX = {A, B, C, D, E, F};
       
edges = [|1, 0, 1, 0, 0, 0, 0, 0, 0
         |1, 1, 0, 1, 1, 0, 0, 0, 0
         |0, 1, 0, 0, 0, 1, 1, 0, 0
         |0, 0, 1, 1, 0, 0, 0, 1, 0
         |0, 0, 0, 0, 1, 1, 0, 1, 1
         |0, 0, 0, 0, 0, 0, 1, 0, 1|];

Solver program:

% Vertices in graph
enum VERTEX;

% Edges between vertices
array[VERTEX, int] of int: edges;

int: num_edges = (length(edges) div card(VERTEX));

% Set of vertices to find
var set of VERTEX: span;

% Number of vertices connected to edge resulting from span
array[1..num_edges] of var 0..num_edges: conn;

% All edges must be connected with at least one vertex from span
constraint forall(i in 1..num_edges)
           (conn[i] >= 1);

% The number of connections to each edge is the number of vertices 
% in span with a connection to that edge
constraint forall(i in 1..num_edges)
           (conn[i] = sum([edges[vert,i]| vert in span]));
           
% Minimize the number of vertices in span
solve minimize card(span);

Solution

  • solve minimize only show one optimal solution (in some cases, intermediate values might also be shown).

    If you want all optimal solutions you must use solve satisfy and add the constraint with the optimal value:

    constraint card(span) = 4;
    

    Then the model outputs all the 6 optimal solutions:

    card(cpan): 4
    span: {A, B, C, E}
    conn: [2, 2, 1, 1, 2, 2, 1, 1, 1]
    ----------
    card(cpan): 4
    span: {B, C, D, F}
    conn: [1, 2, 1, 2, 1, 1, 2, 1, 1]
    ----------
    card(cpan): 4
    span: {A, C, D, E}
    conn: [1, 1, 2, 1, 1, 2, 1, 2, 1]
    ----------
    card(cpan): 4
    span: {B, C, D, E}
    conn: [1, 2, 1, 2, 2, 2, 1, 2, 1]
    ----------
    card(cpan): 4
    span: {A, B, E, F}
    conn: [2, 1, 1, 1, 2, 1, 1, 1, 2]
    ----------
    card(cpan): 4
    span: {B, D, E, F}
    conn: [1, 1, 1, 2, 2, 1, 1, 2, 2]
    ----------
    ==========
    

    Note: I added the output section to show all the values:

    output [
       "card(cpan): \(card(span))\n",
       "span: \(span)\n",
       "conn: \(conn)"
    ];