I have a $16\times11$ matrix and want to find all eligible* combinations of this matrix including always entities from all 11 columns.
A simple example from a $2\times3$ matrix would be the following:
$\begin{bmatrix} 1 & 2 \\ 3 & 0 \\ 5 & 6 \end{bmatrix}$
1,2; 1,0; 1,6;
3,2; 3,0; 3,6;
5,2; 5,0; 5,6
1,3,5 (is for my case, not an option)
*Combinations with 0 entries should get neglected
I have already found a direct algorithm that provides all such combinations Return all combinations from the matrix in Java provided from the user @Niklas Rosencrantz. I have edited the code to fit my case. The problem with this case is it takes too long since I have to use for-loop $16^{11} = 17,592,186,044,416$ times. For an iteration of $10,000,000$ the code needs 25s including reading the data from an Excel file. This means that I need roughly 21 days for the calculation of all data.
I can model the same problem using linear programming. Is there a way to find only the feasible solutions of the problem without searching for the optimal one? I have found documentation in the gurobi site PoolSolutions although I am not sure if this is the best way to search them.
Does it make any sense to use linear programming for this case?
public class main {
private static String excelFileName = "Mappe1 v2.xlsx";
private static int startExcelColumnIndex = 1;
private static int endExcelColumnIndex = 11;
private static int startExcelRowIndex = 1;
private static int endExcelRowIndex = 16;
private static ArrayList<String> stringArrayList = new ArrayList<String>();
private static int maxNumberProviders = 2;
private static List<int[]> combine(int[][] matrix) {
int sizeArray[] = new int[matrix[0].length];
int counterArray[] = new int[matrix[0].length];
long total = 1;
for (int i = 0; i < matrix[0].length; ++i) {
sizeArray[i] = matrix.length; //todo: check this if the following two lines are correct!
total *= matrix.length; // rows^columns
}
// total = 100000000; //fixme: remove this line after checking the
// combinations barier
// List<int[]> list = new ArrayList<>(total);
List<int[]> list = new ArrayList<>();
StringBuilder sb;
String s;
for (long count = total; count > 0; --count) {
// check the number of different providers, using the counterArray
boolean combinationAcceptable = combinationAllowedForMaxNumberOfProviders(counterArray);
boolean combinationPossible;
sb = new StringBuilder();
s = "";
if (combinationAcceptable) {
combinationPossible = true;
for (int i = 0; i < matrix[0].length; ++i) {
if (matrix[counterArray[i]][i]>0) {
sb.append(matrix[counterArray[i]][i]);
s = s + "; " + counterArray[i] + "," + i + "; ";
} else {
combinationPossible = false;
break;
}
}
} else {
combinationPossible = false;
}
if (combinationPossible) {
stringArrayList.add(s);
int tmpi[] = new int[sb.toString().length()];
for (int tmp = 0; tmp < sb.toString().length(); tmp++) {
tmpi[tmp] = Integer.parseInt("" + sb.toString().toCharArray()[tmp]);
}
list.add(tmpi);
} else {
combinationPossible = true;
}
for (int incIndex = matrix[0].length - 1; incIndex >= 0; --incIndex) {
if (counterArray[incIndex] + 1 < sizeArray[incIndex]) {
++counterArray[incIndex];
break;
}
counterArray[incIndex] = 0;
}
}
return list;
}
public static boolean combinationAllowedForMaxNumberOfProviders(int[] counterArray) {
HashSet<Integer> integerHashSet = new HashSet<>();
for (int i = 0; i < counterArray.length; i++) {
int rowIndex = counterArray[i];
integerHashSet.add(rowIndex);
}
if (integerHashSet.size() <= maxNumberProviders) {
return true;
} else {
return false;
}
}
public static void main(String[] args) {
/*int[][] matrix = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};*/
int[][] matrix = new int[endExcelRowIndex][endExcelColumnIndex];
readXlsx(matrix);
int i = 0;
combine(matrix);
writeToTXT();
}
public static void writeToTXT() {
PrintWriter writer = null;
try {
writer = new PrintWriter("MatrixCombinations.txt", "UTF-8");
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
for (String s: stringArrayList
) {
writer.println(s);
}
writer.close();
}
public static void readXlsx(int[][] matrix) {
File myFile = new File(excelFileName);
FileInputStream fis = null;
try {
fis = new FileInputStream(myFile);
} catch (FileNotFoundException e) {
e.printStackTrace();
System.exit(0);
}
// Finds the workbook instance for XLSX file
XSSFWorkbook myWorkBook = null;
try {
myWorkBook = new XSSFWorkbook(fis);
} catch (IOException e) {
e.printStackTrace();
System.exit(0);
}
// read Excel Sheet
XSSFSheet mySheet = myWorkBook.getSheet("Kombinationen");
// Get iterator to all the rows in current sheet
Iterator<Row> rowIterator = mySheet.iterator();
while (rowIterator.hasNext()) {
Row row = rowIterator.next();
if (row.getRowNum() >= startExcelRowIndex && row.getRowNum() <= endExcelRowIndex) {
Iterator<Cell> cellIterator = row.cellIterator();
while (cellIterator.hasNext()) {
Cell cell = cellIterator.next();
if (cell.getColumnIndex() >= startExcelColumnIndex && cell.getColumnIndex() <= endExcelColumnIndex) {
matrix[row.getRowNum()-startExcelRowIndex][cell.getColumnIndex()-startExcelColumnIndex] = (int) cell.getNumericCellValue();
}
}
}
}
}
}
