/*
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.