scc - minimize

[jf]

Hello,

I wonder if there is a way to get scc to minimize
the number of cells set to 1 in the grid.

For example:

   Coords = [(3,2), (4,1), (5,2), (5,5)],
   Dim = 5,
   Board = new_array(Dim,Dim),
   Bvars = Board.vars(),
   Onoff :: [0,1],
   foreach ( (Row,Col) in Coords )
      Board[Row,Col] #= 1,
   end,
   scc_grid(Board),

I would like to test if scc  succeeded with certain number of
vertices not known in advance:

   sum(Bvars) #!= 4 #=> Onoff #= 0

When I try scc_grid(Board, 4) the solver fails.

scc_grid(Board) succeeds and returns any number of vertices satisfying the
constraint, which will not help.

solve([$min(sum(Bvars))], Bvars++[Onoff]) works, but
the solver is called repeatedly.

If scc returned the minimum, the sum(Bvars) test would be possible.

Thank you
Josef

[Neng-Fa Zhou]

Did you notice anything strange? If so, please share your full code. I can only think of modeling the problem as a minimization problem.

Cheers,

NF

--
You received this message because you are subscribed to the Google Groups "Picat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to picat-lang+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/picat-lang/17f7ba3d-584d-4cd6-9c17-aa6ec6d01710n%40googlegroups.com.

[Hakan Kjellerstrand]

Hi Josef.

I'm not sure I understand what you want to do here.

The Coords you are forcing to be set ((3,2), (4,1), (5,2), (5,5)) does not make a strongly connected undirected graph and thus scc_grid(Board,4) - which forces to exactly 4 vertices to be set - will fail.

Here are these coords printed in the matrix.

[0,0,0,0,0]
[0,0,0,0,0]
[0,1,0,0,0]
[1,0,0,0,0]
[0,1,0,0,1]

Using 

   % ...

   scc_grid(Board),

   solve($[min(sum(Bvars))],Vars), 

   % ...

yields this minimal solution:

[0,0,0,0,0]
[0,0,0,0,0]
[0,1,0,0,0]
[1,1,0,0,0]
[0,1,1,1,1]

I.e. it requires 7 1s to be a scc.

Also, what do you mean by "called repeatedly" in

"""

solve([$min(sum(Bvars))], Bvars++[Onoff]) works, but the solver is called repeatedly.
"""

Does your program has some non-deterministic component, such as member/2, which might explain "called repeatedly"?

The problem, as you state it (or rather: as I understand it), does indeed suggest using min() in solve/2.

  

(Also, I'd suggest that you also add the domain to Board:

   % ...

    Board = new_array(Dim,Dim),

    Board :: 0..1,

    % ... ,

though in this case Picat can figure out the domain since scc/1-2 happens to force it to 0..1.

)

Best,

Hakan