/* 

  Set covering problem in Picat.

  This is a rather general model for the following problem.

  From Nathan Brixius
  "Don't be a hero when trying to solve set covering problems"
  http://blogs.msdn.com/b/natbr/archive/2010/06/19/don-t-be-a-hero-when-trying-to-solve-set-covering-problems.aspx
  """
  A colleague posted an interesting question to an internal discussion 
  board the other day:
  
  Given a set of code blocks changed between two versions of the same 
  binary, and approximated code coverage for the new binary, what are 
  the optimal tests that cover all changed part of the new binary and 
  are least costly to run?
  
  Example: (A "1" in a cell (Bi, Tj) means that block i is tested by test j)
      	B1 	B2 	B3 	B4 	B5 	B6 	Cost
  T1 	1 	1 	1 	1 	1 	1 	50
  T2 	0 	1 	1 	1 	1 	1 	20
  T3 	1 	1 	1 	0 	0 	0 	15
  T4 	0 	0 	0 	1 	1 	1 	15

  The optimal solution is T3, T4 with minimized cost 15 + 15 = 30. 
  The best greedy solution that we have is T2, T3 with cost 20 + 15 = 35.

  The colleague who posted this question also posted a mathematical 
  formulation for the problem:

  Binary integer problem statement:

  One constraint for each binary block that needs to be covered to 
  make sure we archive maximum coverage. One variable for each test 
  in the list that we try to optimize.

  Block 1:   X1 + X3 > 0
  Block 2:   X1 + X2 + X3 > 0
  Block 3:   X1 + X2 + X3 > 0
  Block 4:   X1 + X2 + X4 > 0
  Block 5:   X1 + X2 + X4 > 0
  Block 6:   X1 + X2 + X4 > 0

  X1, X2, X3, X4 = {0, 1}

  Cost function to optimize: 50*X1 + 20*X2 + 15*X3 + 15*X4
  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


import cp.

main => go.


go =>

  TCosts = [50,20,15,15],
  Mat = [
         [1,1,1,1,1,1],
         [0,1,1,1,1,1],
         [1,1,1,0,0,0],
         [0,0,0,1,1,1]
        ],
  
  NumT = Mat.length,
  NumB = Mat[1].length,

  X = new_list(NumT),
  X :: 0..1,

  TotalCost #= sum([X[I]*TCosts[I] : I in 1..NumT]),
  foreach(J in 1..NumB) 
      sum([X[I]*Mat[I,J] : I in 1..NumT]) #>= 1
  end,

  solve($[min(TotalCost)], X),

  println(totalCost=TotalCost),
  println(x=X),

  nl.