blob: ecbcdaa5bd29a30b0d9090acfcea7e2b97a85a78 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import Numeric.LinearProgramming
-- This is a linear program from the paper "Picking vs. Guessing Secrets: A Game-theoretic Analysis"
gamma = 100000 :: Double
sigma = 1 :: Double
n = 64 :: Int
cost_fun :: Int -> Double
cost_fun i = (fromIntegral i) / (fromIntegral n)
size_fun :: Int -> Double
size_fun i = 2^(fromIntegral i)
prob = Minimize $ map cost_fun [1..n]
bnds = [i :&: (0,1) | i <- [1..n]]
constr1 = [[1 # i | i <- [1..n]] :==: 1] ++
[[1/(size_fun i) # i,
-1/(size_fun (i+1)) # i+1] :>=: 0 | i <- [1..n-1]] ++
[(
[gamma#i | i <- [1..k]] ++
(concat [[sigma*(size_fun i) # j | j <- [1..i-1]] | i <- [1..k]]) ++
[((size_fun i) - 1)/2 # i | i <- [1..k]])
:<=: (sigma * (foldr (+) 0 (map size_fun [1..k]))) | k <- [1..n]]
main = do
print $ simplex prob (General constr1) bnds -- NoFeasible
print $ exact prob (General constr1) bnds -- solution found
|
