Originally posted by: ReneGusmao

Hi there, I have a model implemented in OPL. I want to use this model to implement a local search in java. I want to initialize solutions with some heuristics and give these initial solutions to cplex find a better solution based on the model, but also I want to limit the search to a specific neighborhood. Any idea about how to do it?

Thanks in advance!

Rene

You can use OPL directly from Java. See the examples in CPLEX_INSTALL_DIR/opl/examples/opl_interfaces.

In order to set a starting solution either use IloCplex.addMIPStart() (in Java) or IloOplCplexVectors (in OPL). For the latter see example opl/examples/opl/warmstart.

In order to restrict CPLEX to a certain neighborhood you could fix all variables that must not change (or limit their range). Of course not every neighborhood can be defined in that way.

Originally posted by: ReneGusmao

Hi again! Very thanks for your reply! How can I limit the range of all variables?

Also, what's the best: implement these heuristics and local search in own opl or in java or even C++?

In order to limit the range of a variable x just change its bounds (using setLB() or setUB() member function) or add a constraint like "x >= 3" or "x <= 5".

What language to choose depends on how familiar you are with them. Java and C++ will probably be a little faster than OPL, but OPL (and OPL script) may be simpler to write.

Originally posted by: ReneGusmao

Thanks again for your response!! In my model, most of the decision variables are binary, in this case, how can I limit the step between the solutions generated (something like solution1 differs from solution2 in 15 variables)? 

Let me try to be more clear: I am working with a NP-Complete problem. Cplex deals well with little instances of this problem. I want to implement a metaheuristic to solve it for bigger instances. I want to implement a heuristic (in java) to give initial solutions, load this initial solution to the model in opl so it can works like a local search.

Again, thank you for your help.

Assume you have an array x[] of binary variables that is indexed by I. Also assume that xnow[] is the current feasible solution. Then

  sum (i in I : xnow[i] == 1) (1-x[i]) + sum(i in I : xnow[i] == 0) x[i]

gives the number of variables in x that differ from xnow. With that you can limit the number of variables that are different between xnow and the next solution.

Originally posted by: ReneGusmao

I have another question: my model implemented in OPL and solved by CPLEX, for some instances it takes 3-4 secs to solve and for anothers it takes hours (I havent checked it, I got out of memory). Why is that? My model is wrong?

Originally posted by: TobiasAchterberg

This question cannot be answered without getting the problem data. Since MIP is NP-hard, it could very well be the case that some data sets lead to an easy problem instance while others lead to a difficult problem instance.

Originally posted by: ReneGusmao

And how can I be sure that my model is implemented right?

Originally posted by: TobiasAchterberg

Well, this is the art of modeling. You need to understand your model and verify that your constraints do what they should.

If you have some data sets for which you know feasible solutions, then you can test your model by fixing the variables to the corresponding solution values and then verifying that the resulting fixed model is feasible.

Originally posted by: ReneGusmao

My model has four decision variables:

I want to use a heuristic and provide only starting values for xd, is that possible? If yes, how can I do it using IloCplex.addMIPStart()?

MIP starts can be partial, so it is possible to provide only starting values for xd. CPLEX will spend a limited effort in trying to find values for the remaining variables.

To specify a MIP start in OPL you need to use the IloOplCplexVectors class. See the opl/examples/opl/warmstart example in the CPLEX distribution.

Originally posted by: ReneGusmao

And how can I set only xd in java?

Originally posted by: ReneGusmao

Hi, can I tell to cplex works like a heuristic and allocate demands like a first fit heuristic allocating based on an order and returning this solution??

Thank you.

Originally posted by: TobiasAchterberg

I don't know if I understand the question. You can specify a branching priority order to tell CPLEX to branch on variables in a particular order. Moreover, you can set the branching direction, for example to always branch up first. Please see the user's manual and parameter reference manual for further details.

Originally posted by: ReneGusmao

I have my model minimize objective funtion and my constraints, I want to add some constraints setting some demands which will be rejected. For example, suppose a set of demands d1,d2, .., d10. I want to add constraints to rejects demands d1 and d2 setting xd[d1] ==1 and xd[d2]==1 in constraints. How can I do it in main script? Also in another iteration I want to be able to change the demands which I want to reject.

Originally posted by: ReneGusmao

Can you explain a little better this expression? I have to add this constraint in the opl model or inside the main script? xnow will be a decision variable too?

sum (i in I : xnow[i] == 1) (1-x[i]) + sum(i in I : xnow[i] == 0) x[i]

Suppose that I start with a solution xd[d in Demands] = [0,0,0,0,1,1,0,0,0,1] for a set of 10 demands. 0 means allocated demand and 1 means rejected demands. So now I want to explore the neighborhood of this solution, but I want to limit the cplex search to solutions which changes by only two demands allocated or not. How can I do it? 

Whether you add this to the main() script or the model depends on whether you have the solution xd a priory or if that is a solution that is dynamically computed by CPLEX.

Assuming you have xd a priory and the variables in your model binary you can just add the following constraint to the model:

sum(d in Demands : xd[d] == 1) (1 - x[d]) + sum(d in Demands : xd[d] == 0) x[d] <= 2;

This will allow at most two variables in x[] to be different from the values in xd[].

Originally posted by: ReneGusmao

I've tried it, but I got the error "Decision variable (or expression) "xd" not allowed. x[d] is also a decision variable? My objective function is minimize sum (d in Demands) xd[d] *d.bd, in which d.bd is the bandwidth of the demand.

Originally posted by: ReneGusmao

In OPL Main Script, how can I add a constraint setting some values of xd[d] that must not change? I want use this same idea when providing initual solutions.

Basically you have to add an empty constraint in the original model that you can then update in your script. Here is a small example that implements that:

range Demands = 1..10;
dvar boolean xd[Demands];

maximize sum(d in Demands) xd[d];

subject to {
  // This is a constraint that is redundant by default.
  // In the scripting block we dynamically change its coefficients
  // to turn it into a constraint that really does something.
  limitRange: sum(d in Demands) xd[d] <= infinity;
}

main {
  // Do a first solve.
  thisOplModel.generate();
  cplex.solve();
 
  // Save the current solution into an array. Note that arrays
  // are indexed starting from 0. Since Demands runs from 1 through N,
  // we must subtract 1 from d.
  var x = new Array(thisOplModel.Demands.size);
  for (var d in thisOplModel.Demands) { x[d-1] = thisOplModel.xd[d].solutionValue; }
 
  // Now change limitRange so that at most two variables can
  // be different from the values in x[]. The constraint we
  // establish is
  // sum(d in Demands : xd[d] == 1) (1 - xd[d])
  //    + sum(d in Demands : xd[d] == 0) xd[d]
  //    <= 2
  var rhs = 2; // At most 2 variables can change.
  for (var d in thisOplModel.Demands) {
    if (x[d-1] > 0.5) {
      // xd[d] is 1 -> add term (1 - xd[d]), that is, add -xd[d] on the
      //               left-hand side and -1 on the right-hand side.
      cplex.setCoef(thisOplModel.limitRange, thisOplModel.xd[d], -1);
      rhs -= 1;
    }
    else {
      // xd[d] is 0 -> add term xd[d]
      cplex.setCoef(thisOplModel.limitRange, thisOplModel.xd[d], 1);
    }
    thisOplModel.limitRange.UB = rhs;            
  }    
 
  // Now a second solve with the modified model.
  cplex.solve();
  0;
}

Originally posted by: ReneGusmao

I've added created another set of Demands called SelectedDemands and added a constraint

forall(d in SelectedDemands) xd[d] ==1; //forcing these demands to be rejected or served if equal to 0

In main script I manipulate which demands are in SelectedDemands, but it seems that this constraint isnt being respected, if I set some demands to be rejected, cplex solves and give me a solution with these demands served if possible.

What's wrong?

I am not an OPL expert. Maybe try the OPL Forum with this question.

I think that changing the elements in the SelectedDemands set will not work. Instead you should change the coefficients in the constraint as I did in the example I showed (set the coefficient of xd[d] to 1 if d is in SelectedDemands and to 0 otherwise).

Originally posted by: ReneGusmao

I have my model minimize objective funtion and my constraints, I want to add some constraints setting some demands which will be rejected. For example, suppose a set of demands d1,d2, .., d10. I want to add constraints to rejects demands d1 and d2 setting xd[d1] ==1 and xd[d2]==1 in constraints. How can I do it in main script? Also in another iteration I want to be able to change the demands which I want to reject.

Have you tried using the LB and UB property of IloNumVar? As in

   xd[d1].LB = 1;
   xd[d1].UB = 1;

That should fix the variable to 1.

Originally posted by: ReneGusmao

Hello, Is it possible to save a solution provided by CPLEX, after it CPLEX run again and analyze whether the current solution is better than the previous? This way, if my main script has 10 iterations, I would like to evaluate each step the best and in the end have the best of 10.

You can post process any feasible solution that CPLEX finds, see the covering example, in patricular the section about post processing. In the post processing function you can for example store the solution on disk (or somewhere else) and then in the next iteration read it back in.

You can also just store the best solution found and in the post processing function overwrite it only with improving solutions.

Originally posted by: ReneGusmao

Hi Daniel, thanks again for your reply.

"You can also just store the best solution found and in the post processing function overwrite it only with improving solutions."

How can I do that?

Here is a short example that stores every solution in a different file. From this it should be easy to figure out how to keep track of the best solution found so far.

range R = 1..10;

dvar boolean x[R];
dexpr float objval = sum(r in R)r*x[r];

maximize objval;

subject to {
  sum(r in R) x[r] <= 3;
}
execute POSTPROCESS {
  // Find a new unique name for the output file.
  // This is very crude, has a race condition, etc.
  // but should do for illustration.
  var name = null;
  for (var i = 0; true; ++i) {
    name = "file" + i;
    var f = new IloOplInputFile(name);
    if (!f.exists)
      break;    
    else
      f.close();
  }
  // Store the solution in a file.
  writeln("Storing solution in " + name);
  var out = new IloOplOutputFile(name);
  out.writeln("objective = " + objval);
  for (r in R) {
    out.writeln("x[" + r + "] = " + x[r]);  
  }
}

Originally posted by: elen_can

Hi Daniel,

I would like to implement a local search algorithm for my MIP model implemented on docplex. Is it possible to do this using Python? I found a document named "CPLEX library MIP Heuristics" but nothing is clear on that. I really appreciate it if you help me regarding the Combining Local Search and MIP Heuristics in Cplex.

Many thanks in advance.

Yes, this can be done (however, you should have started a new thread).

However, writing a local search is sort of unrelated to docplex (unless you want to extract the model from docplex and write a generic local search for this).

You can implement your local search in Python and then submit feasible solutions either as MIP starts or from a heuristic callback.

Originally posted by: elen_can

Thank you very much.

Is there any example code on how to callback a heuristic using python Cplex. Because I couldn't find any example of combining local search (or any other heuristics) and MIP in Cplex.

Could you please also share with me an example code that is doing post-processing in docplex?

I really appreciate your help in advance.

Elen

Originally posted by: p_couronne

Hi Elen,

Here is an example showing how to interact with a heuristics callback from within docplex.

It uses a mixin code in the process of being documented, so let me know if you have any questions.

The same code is used to interact with other types of legacy callbacks (e.g. mip info callbacks, , lazy callback, cut callbacks...)

As for post-processing, I'm not sure what you mean in this context, so can you explain what you want to do?

Is this related to solutions?

  Hope this helps.

     Philippe.

Originally posted by: elen_can

Hi Philippe,

Thank you very much for your response.

Regards,

Elen