Originally posted by: Jernej1
This is a continuation of this post, where I received many useful responses. Here I would like to expand the post by providing some more insight into the problem and what I tried so far.
The problem. Find a set S of 119 binary strings of length 10 so that every binary 10-string has a member in S that differs from it in at most one bit.
In addition, we are given a sequence (from now on configuration) of 2^K (here K=3) integers x_1,...,x_{2^k} and the number of elements of S that have i (0<=i<2^k) as a prefix (i is treated in binary form) is x_i.
We say that a configuration is infeasible if the underlying ILP is infeasible.
Motivation. The idea is to try to compute the next member of the sequence, A000983 which is an open problem in coding theory for almost two decades.
The code pasted bellow solves the specific problem described above. It accepts a file where every line contains a configuration sequence delimited by the dash symbol and tries to solve the underlying ILP.
I have a starting file with 585090 non-isomorphic configurations and my aim is to reduce it as much as possible. It is not necessary to fully reduce the configurations as there are other steps to this process,
but doing so would immediately give that A000983(10) = 120. Generally though, the more configurations that are proven infeasible at this stage, the easier it gets later on.
Right now CPLEX was able to reduce 47.5% of these configurations resulting in a file of 306679 configurations (attached as k3infeasreduced.txt).
Experimenting extensively with CPLEX parameters I concluded that having CPXPARAM_Emphasis_MIP:=CPX_MIPEMPHASIS_BESTBOUND is by far the most significant parameter setting. This reduced the vast majority of configurations extremely quickly. It was a real game changer. I am a bit puzzled how a parameter that is expected to rely on moving the best bound had such a significant effect on a model with no objective function at all?
The second best parameter to set seem to be CPXPARAM_MIP_Strategy_StartAlgorithm=CPXPARAM_MIP_Strategy_SubAlgorithm := CPX_ALG_PRIMAL, and I have no idea why.
As Daniel Junglas pointed, it also makes sense to set CPXPARAM_MIP_Strategy_HeuristicFreq := -1 and this is the third best parameter to set.
I've also tried setting various combinations for CPXPARAM_MIP_Strategy_VariableSelect and CPXPARAM_MIP_Strategy_Probe parameters but with no empirical success.
Finally, I've tried the tuning tool on a large sample of configurations (with various pre-set parameters) and for the most part it is suggesting to set CPXPARAM_MIP_Limits_CutPasses=1 and CPXPARAM_MIP_Strategy_VariableSelect=CPX_VARSEL_PSEUDOREDUCED. I was able to get some further reductions using this parameter set, but nothing significant.
Intuitively, it seems clear that if the configuration is "imbalanced" then the underlying ILP is easily proved to be infeasible. Indeed it took less than 6900 ticks (5s) to prove the infeasibility of 39-8-7-13-7-13-21-11 and 39-13-8-12-8-12-16-11. However, the configuration 39-8-8-15-8-14-14-13 was not proven to be infeasible even after 1M ticks and trying an extensive plateau of cplex parameters. I am curious to see if anybody is able to prove its infeasibility?
On the other side the of the spectrum, the "balanced" configurations 17-17-16-16-17-14-11-11 and 17-17-17-15-15-16-11-11 were proven infeasible in about 20000 ticks (120s). See also the attached log files.
The average number of ticks it took to prove infeasibility for all the configurations so far was 50200 (131s). The quickest to be computed was the configuration 7-21-31-8-22-9-8-13, proven infeasible in 3740.65 ticks and the longest configuration was 11-14-36-8-14-14-8-14 with 117575447 ticks. Note that for the most part I had a limit of 100k ticks per computation and only spent extra time with a small sample of configurations.
The respective log files of all mentioned configurations are attached as well as the log files for all configurations proven infeasible is available separately.
Currently I am running the program bellow, with the parameter CPXPARAM_RandomSeed set to a random number at runtime and a 1hour time limit per configuration. I am able to get about 0.5% reduction in the number of configurations after each iteration of the program on the file k3infeasreduced.txt. I wonder, is there any other way to leverage randomness in this model/the respective solver?
At this point my knowledge stops. I am curious to hear if there are other parameter settings I could explore, or perhaps some other ways to attack this problem? Given my current computational capacity, this problem does not seem out of reach, but it would be extremely beneficial If I could find a way to further reduce the configurations left in k3infeasreduced.txt. Can I perhaps add some objective function or constraint that could improve the process of proving infeasibility?
Given how quickly CPLEX manages to prove infeasibility of certain parameters I feel very confidently there has to be ways to reduce the number of configurations even further. I have at my disposal a large computational grid and I am open to try any constructive suggestions.
#include <string.h>
#include <iostream>
#include <fstream>
#include <random>
#include <stdio.h>
#include <ilcplex/ilocplex.h>
#define N 10
#define K 3
#define CONF_SIZE ( 1<<K )
#define TICK_LIMIT 100000
IloEnv env;
void write_configuration(FILE *out, const unsigned *d, const unsigned n);
unsigned int read_configuration(FILE *in, unsigned *d, const unsigned n);
/* This function returns 0 if it could not prove that the given
* configuration is infeasible, nozero otherwise
*/
static unsigned isInfeasible(const unsigned d[CONF_SIZE]) {
unsigned i,j;
int status;
std::random_device rd;
std::mt19937 rng(rd());
std::uniform_int_distribution<int> uni(0,1<<23);
auto random_integer = uni(rng);
try {
IloModel model(env);
IloNumVarArray var(env);
IloRangeArray con(env);
IloCplex cplex(model);
/* MAIN SETTINGS */
cplex.setParam(IloCplex::Param::MIP::Strategy::HeuristicFreq, -1);
cplex.setParam(IloCplex::Param::DetTimeLimit, TICK_LIMIT);
cplex.setParam(IloCplex::Param::Emphasis::MIP, 3);
cplex.setParam(IloCplex::Param::NodeAlgorithm, 1);
cplex.setParam(IloCplex::Param::MIP::Strategy::PresolveNode, 1);
cplex.setParam(IloCplex::Param::RootAlgorithm, 1);
cplex.setParam(IloCplex::RootAlg, 1);
cplex.setParam(IloCplex::Param::Threads, 1);
cplex.setParam(IloCplex::RandomSeed, random_integer);
/* MAIN SETTINGS */
for (i = 0; i < (1U<<N) ; i++) {
var.add( IloBoolVar(env));
}
for (i = 0; i < (1U << N) ; i++) {
IloExpr expr(env);
expr = var[i];
for (j = 0; j < N; j++) {
expr += var[i ^ (1<<j)];
}
con.add( expr >= 1 );
}
for (i = 0; i < CONF_SIZE; i++) {
IloExpr expr(env);
for (j = 0; j < (1U << (N-K) ); j++) {
expr += var[ (j << K) | i ];
}
con.add( expr == d[i] );
}
model.add(con);
cplex.solve();
if ( cplex.getStatus() == IloAlgorithm::Infeasible ) {
return 1;
}
} catch(IloException& e) {
std::cerr << "Concert exception caught: " << e << std::endl;
}
catch(...) {
std::cerr << "Unknown exception caught" << std::endl;
}
return 0;
}
int main(int argc, char **argv) {
int status;
if (argc != 2) {
fprintf(stderr, "Incorrect usage of comand line arguments\n");
exit(EXIT_FAILURE);
}
FILE *in, *out;
in = fopen(argv[1], "r");
assert(in != NULL);
char buf[512];
sprintf(buf, "%s.out", argv[1]);
out = fopen(buf, "w");
unsigned d[1<<K];
while (!feof(in)) {
if (!read_configuration(in, d, 1U<<K)) {
printf("============================================== Processing configration ");
write_configuration(stdout, d, 1U<<K);
if (!isInfeasible(d)) {
write_configuration(out, d, 1U<<K);
} else {
printf("Found one infeasible configuration: ");
write_configuration(stdout, d, 1U<<K);
}
}
}
fclose(in);
fclose(out);
return 0;
}
void write_configuration(FILE *out, const unsigned *d, const unsigned n) {
unsigned int i;
for (i = 0; i < n-1 ; i++) {
fprintf(out, "%u-", d[i]);
}
fprintf(out, "%u\n", d[i]);
}
unsigned int read_configuration(FILE *in, unsigned *d, const unsigned n) {
unsigned int i;
char c;
for (i = 0; i < n; i++) {
if ( fscanf(in, "%u%c", &d[i], &c) != 2) {
return 1;
}
}
return 0;
}
#CPLEXOptimizers#DecisionOptimization