I am trying to figure out all possible combinations of packaging items together. Basically it's an integer programming problem where you have i number of items, j number of boxes and binary variable x[i,j].
There are many constraints, but I built a simple problem with one volume constraint first, which is the sum of volume of items assigned to box j cannot exceed the volume of box j.
I need all feasible solutions for this constraint. I used AMPL with cplex but there is no cplex option for finding all feasible points.
I wonder if it is possible to get all feasible solutions using lpSolveAPI package using R. I attach my AMPL codes below for better understanding. Thank you.
set items;
set containers;
param items_vol {i in items};
param containers_vol {j in containers};
var x{i in items, j in containers} binary;
var y{j in containers} binary;
minimize containers_volume: sum{i in items, j in containers}
containers_vol[j] * x[i,j];
subject to volumes {j in containers}:
sum {i in items} x[i,j] * items_vol[i] <= containers_vol[j];
subject to usage {i in items}:
sum {j in containers} x[i,j] = 1;
subject to usage2 {j in containers}:
y[j] - sum{i in items} x[i,j] <= 1
There are two different approaches to enumerate all feasible integer solutions.
The first is to add a cut to the constraints that forbids the previously found solution. I.e.
1. solve problem
2. if infeasible: done
3. record optimal solution x[i] into a[i]
4. add cut of the form
sum(i, (2*a[i]-1)*x[i]) <= sum(i,a[i])-1
5. go to step 1.
I assumed here the binary variables are x[i].
The second approach is to use the Cplex solution pool. This is much faster if there are many solutions.
PS: LpSolveApi documents things like get.solutioncount and select.solution. I don't think that actually works.