Generate feasible solutions to a knapsack problem using Markov Chain Monte Carlo

Share:

Description

Generate feasible solutions to a knapsack problem using Markov Chain Monte Carlo

Usage

1
sampl.mcmc(init, numSampl, maxIter = 2 * numSampl, constraints = NULL)

Arguments

init

- an initial feasible solution

numSampl

- number of samples to be generated

maxIter

- maximum number of iterations to be run to prevent infinite loop

constraints

- a list of list of constraints with constr.mat, constr.dir, constr.rhs in each sublist Please see example for an example of constraints.

Value

a matrix of 0, 1 with each row representing a sample

Examples

 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
#number of variables
N <- 100

#number of variables in each group
grpLen <- 10

#equality matrix
A <- matrix(c(rep(1, N)), ncol=N, byrow=TRUE)

#inequality matrix
G <- matrix(c(rep(1, grpLen), rep(0, N - grpLen),
    rep(c(0,1), each=grpLen), rep(0, N - 2*grpLen)), ncol=N, byrow=TRUE)

#construct a list of list of constraints
constraints <- list(
    list(constr.mat=A, constr.dir=rep("==", nrow(A)), constr.rhs=c(20)),
    list(constr.mat=G, constr.dir=rep("<=", nrow(G)), constr.rhs=c(5, 5)),
    list(constr.mat=G, constr.dir=rep(">=", nrow(G)), constr.rhs=c(1, 2))
)

#generate an initial feasible solution
init <- initState(N, constraints=constraints)

#create feasible solutions to knapsack problems subject to constraints
samples <- sampl.mcmc(init, 50, constraints=constraints)