Originally posted by: albertschrotenboer

Hello all,

I have implemented a heuristic callback, in which I want to set a new incumbent solution. I've done this by using the SetBounds() -- solve() -- setSolution() paradigm, and I check whether the variables are implied integer etc. Code looks like this:
for (int i = 0; i != nvars; ++i)
  {
    if (feas[i] == CPX_IMPLIED_INTEGER_FEASIBLE)
    {
      vars1.add(vars[i]);
      vals1.add(vals[i]);
      setBounds(vars1[i], vals1[i], vals1[i]);
    }
  }

if (solve())
    setSolution(vars1, vals1);
 

Then, a ``strange" thing happens. The feasibility of the solution depends on the node it currently processed (from which the heuristic callback is called). So, after 20 times calling this callback suddenly the proposed solution becomes a feasible one, instead of an infeasible one. Note that I am 100% sure that the solution is a correct one, as it follows from solving a relaxed model. Actually, it makes a lot of sense as due to branching and preprocessing the proposed solution might not make sense at all. 

My question is as follows: Is there a way to input a feasible solution during the MIP solve which does not depend on local information of a node, i.e., similar to feeding a solution before solving starts but then during the mip solve? Now I am calling this heuristic callback way more then needed, as it rejects my solutions for a steady amount of iterations until it accepts the solution.

Thanks in advance,

Albert

Is that just typo here or is your code wrong? Shouldn't you be using '!=' instead of '==' when checking whether you want to call setBounds() on a variable? From the code you posted it seems like you are trying to fix exactly those variables that are already fixed.

How do you detect that the solution is considered infeasible? Is it because solve() returns false or is it because the respective objective value does not appear in the log?

Does your model contain any constraints that are not just plain linear constraints. Do you use logical constraints, IloIfThen or anything similar?

Do things work any better if you disable dual and/or non-linear reductions?

Originally posted by: albertschrotenboer

I'm sorry, that was a typo. I've copied the code below. We detect that they are infeasible because solve() returns false. We only have linear constraints (via lazy and user callbacks as well as via a lazy constraint pool and a set of initial (also linear) constraints). I think dual reductions are disabled due to using lazy callback. 

I suspect solve() returns false because the solution is infeasible in that specific node of the b&b tree from which the heuristic callback is called, while the solution is feasible without branching/preprocessing? constraints/decisions. 

The code:  g_globalSol is a thread safe vector<vector<double>> describing our solution, and model is an Object defining that encapsulates all constraints, variables and problem data.

  IloNumArray vals    = IloNumArray(model.d_env);
  IloNumVarArray vars = IloNumVarArray(model.d_env);
  int obj = 0;

  for (int i = 0; i != model.d_nNodes; ++i)
  {
    for (int j = 0; j != model.d_nNodes; ++j)
    {
      int value = g_globalSol[i][j]._a;

      if (value == 1 )
      {
        vals.add(g_globalSol[i][j]._a);
        vars.add(model.d_x[i][j]);
        obj += g_globalSol[i][j]._a * model.d_cost[i][j];
      }
    }
  }
    
 
  IntegerFeasibilityArray feas = IntegerFeasibilityArray(model.d_env);
  getFeasibilities(feas, vars);

  IloNumArray vals1 = IloNumArray(model.d_env);
  IloNumVarArray vars1 = IloNumVarArray(model.d_env);
  
  int nvars = vars.getSize();
  
  
  for (int i = 0; i != nvars; ++i)
  {
    if (feas[i] != CPX_IMPLIED_INTEGER_FEASIBLE)
    {
      vars1.add(vars[i]);
      vals1.add(vals[i]);
      setBounds(vars1[i], vals1[i], vals1[i]);
    }
  }
   
  if (solve())
    setSolution(vars1, vals1);

  vals.end();
  vars.end();
  
  vals1.end();
  vars1.end();
  feas.end();
  

The problem is the way in which you use the solve() function. According to the reference documentation:

This method can be used to solve the current node relaxation, usually after some bounds have been changed by HeuristicCallbackI::setBounds. By default it uses the dual simplex algorithm, but this behavior can be overridden by the optional parameter alg. See the enumeration IloCplex::Algorithm for a list of the available optimizers.

So the function will return false unless your solution is feasible within the local bounds of the current node and with respect to the current node's relaxation (which may include (local) cuts). I guess that explains why your solution only becomes feasible eventually.

Since you know that your solution is feasible, can you just inject it without testing feasibility with solve()? Does that work any better?