Thank you very much! I have learned a lot!
Thank you very much! I have learned a lot! It's very interestring to discuss with you.
I still think CPLEX has some troubles handling decimals.I will try my best to expain.
I have 3 TSP instances(Let's call them A,B,and C).Only A has fractional distance matrix.
At first,I try to solve TSP using constraint generation(without callback).First, I model it as an Assignment Problem，solve it ,find all the subtours, generate constraints to eliminate subtours and add them to the model,and solve the model again(using a while loop. If there is no subtoor, the program ends). The program can handle instance B,C real quickly(and I get the correct answers), but it stuck when it comes to instance A. After I truncate the data to integer, everything is OK. Here is the CPLEX log where it stucks.
Then, I try to solve TSP using Lazycallback.Again, I model it as an Assignment Problem, using lazycallback to eliminate subtours.It results that: solving B,C real quickly. But I get error 1217 with the original distance matrix of instance A.After I truncate the data to integer, everything is OK.
At last, I try to solve TSP using generic callback. I encounter excatly the same problem : error 1217 with original data ... and everything is OK after I truncate the data to integer.
What's more,it reminds to me that I once met similar problem when I used column generation to solve VRPTW.When it comes to calculate and compare the Reduced Cost , it seems necessary to truncate.Otherwise, the solve time is extremely slow.
That's why I think CPLEX may have some troubles handling decimals. I am looking forward to you reply!
------------------------------
Jixuan Feng
------------------------------
Original Message:
Sent: Fri October 21, 2022 03:28 PM
From: Paul Rubin
Subject: Java API- Question on generic callback implementation
There is no reason why objective values with fractional coefficients would cause CPLEX to generate a candidate solution that violated any of the constraints. When you round/truncate the objective coefficients to integer, you change the model, which may lead to different results. So possibly you have a problem in the model that still remains, but the change leads CPLEX to a different trajectory on this particular model instance that (by luck) avoids the problem.
I have never used the code structure you are using (making the callback a static subclass, making the master IloCplex object a local variable in a method rather than a class field and then having to recover it in the callback with context getCplex() method, ...), so it's hard for me to see if this would cause thread safety errors. The only class variable in the callback, x, is written to only in the constructor, with all other variable changes occurring to variables local to the invoke method, so I don't see much potential for thread collisions ... but I'm no expert on thread safety either. If you are getting error 1217 with the original distance matrix but not with the integer distance matrix, I would suggest the following experiment:
- solve with the integer distances and record the solution (call it "sol1");
- return the distance matrix to the original double precision values, and in the code setting up the model fix every variable to its value in "sol1" (by setting lower bound = upper bound = value for each variable);
- solve again and, if error 1217 occurs, try to get a minimal conflict set, which will identify which constraints are not satisfied by "sol1".
If "sol1" ends up satisfying the original constraints but violating one of the Benders cuts, then you need to see whether your subproblem is generating incorrect Benders cuts for some reason.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Fri October 21, 2022 12:45 AM
From: Jixuan Feng
Subject: Java API- Question on generic callback implementation
Hi Mr. Rubin!
I think I know what is happening! The data is to accuracy, which may cause problem when cplex is handling floating point number!
Here is a glance of the distance matrix.Afrer I transform it to integer, everything is ok!
Anyway， Thanks for your time! I learned a lot from you replies and your blogs!!
------------------------------
Jixuan Feng
Original Message:
Sent: Thu October 20, 2022 05:37 PM
From: Paul Rubin
Subject: Java API- Question on generic callback implementation
Immediately after calling the callback constructor, you have System.exit(0). The program should stop there, which is a bit of a conundrum. Besides that, can you reproduce the problem with a smaller test example and, if so, post the output obtained when printing the values of x[][] in the callback?
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Thu October 20, 2022 06:52 AM
From: Jixuan Feng
Subject: Java API- Question on generic callback implementation
I am solving traveling salesman problem(tsp),and I I am using generic callback implementation for subtour elimination.
Everythin is fine when I used Lazycallback(legacy callback),but when i am trying to use generic callback,I find that context.getCandidatePoint x[i][j] has problem.Results shows that sometimes I will encounter such a situation: for vertex i ,its indegree/outdegree ==0 or 2.I wonder why.
Thanks!
Here is my code.
package benders;
import ilog.concert.*;
import ilog.cplex.IloCplex;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
/**
* @Author: Feng Jixuan
* @Date: 2022-10-2022-10-20
* @Description: algorithm
* @version=1.0
*/
public class Test {
static int n = 127;
static double[][] distance = new double[n][n];
static double cost;
static double[][] ans = new double[n][n];
static double[] tour = new double[n];
static ArrayList<Integer> subTour;
static ArrayList<ArrayList<Integer>> subTourPool;
static int run = 0;
public static void main(String[] args) throws IloException, IOException {
String path = "tsp" + n + ".txt";
BufferedReader br = new BufferedReader(new FileReader(path));
String line = null;
int count = 0;
while ((line = br.readLine()) != null) {
String[] str = line.split("\\s+");
for (int i = 0; i < n; i++) {
distance[count][i] = Double.parseDouble(str[i]); //
}
count++;
}
long startTime = System.nanoTime();
IloCplex cplex = new IloCplex();
IloIntVar[][] x = new IloIntVar[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j)
x[i][j] = cplex.intVar(0, 1, "x" + i + "," + j);
else
x[i][j] = cplex.intVar(0, 0, "x" + i + "," + j);
}
}
for (int i = 0; i < n; i++) {
IloLinearIntExpr constraint = cplex.linearIntExpr();
for (int j = 0; j < n; j++) {
constraint.addTerm(x[j][i], 1);
}
cplex.addEq(cplex.sum(x[i]), 1, "outDegree " + i);
cplex.addEq(constraint, 1, "inDegree " + i);
}
IloLinearNumExpr obj = cplex.linearNumExpr();
for (int i = 0; i < n; i++) {
obj.add(cplex.scalProd(x[i], distance[i]));
}
cplex.addMinimize(obj);
cplex.exportModel("test.lp");
MyCallback callback=new MyCallback(x);
System.exit(0);
cplex.use(callback,IloCplex.Callback.Context.Id.Candidate);
// cplex.use(new MyCallback(x,cplex));
cplex.solve();
System.out.println(cplex.getObjValue());
long endTime = System.nanoTime();
System.out.println("Time cost=" + (endTime - startTime) / 1000000000.0 + "s");
}
private static class MyCallback implements IloCplex.Callback.Function {
private final IloIntVar[][] x;
// IloCplex cplex;
private ArrayList<Integer> subTour;
private ArrayList<ArrayList<Integer>> subTourPool;
private double[][] arcs;
private MyCallback(IloIntVar[][] x) {
this.x = x;
}
public void invoke(IloCplex.Callback.Context context) throws IloException {
if (context.inCandidate()) {
arcs = new double[n][n];
for (int i = 0; i < n; i++) {
arcs[i] = context.getCandidatePoint(x[i]);
}
for (int i = 0; i < n; i++) {
System.out.print(Arrays.toString(arcs[i]));
for (int j = 0; j < n; j++) {
if (arcs[i][j]>0.9) System.out.print(i+"_"+j);
}
System.out.println();
}
IloCplex cplex=context.getCplex();
if ( !context.isCandidatePoint() )
throw new IloException("Unbounded solution");
if (!checkSubTour()) {
while (!subTourPool.isEmpty()) {
subTour = subTourPool.get(0);
subTourPool.remove(0);
IloLinearNumExpr constraint2 = cplex.linearNumExpr();
System.out.println(subTour.toString());
for (int i : subTour) {
for (int j : subTour) {
constraint2.addTerm(1, x[i][j]);
}
}
System.out.println("Adding lazy capacity constraint " + constraint2 +"<="+
(subTour.size() - 1));
context.rejectCandidate((IloRange) cplex.le(constraint2, subTour.size() - 1));
}
}
// cplex.exportModel("test"+n+"_"+run+".lp");
}
}
public boolean checkSubTour() {
run++;
System.out.println("------------------" + run + "-----checkSubTour-----------------------");
subTourPool = new ArrayList<ArrayList<Integer>>();
int[] visited = new int[n];
for (int i = 0; i < n; i++) {
if (visited[i] == 1) {
continue;
}
subTour = new ArrayList<Integer>();
int cur = i;
System.out.println("break");
do {
subTour.add(cur);
visited[cur] = 1;
boolean f=false;
for (int j = 0; j < n; j++) {
if (arcs[cur][j] > 0.9) {
cur = j;
break;
}
}
} while (cur!= i);
subTourPool.add(subTour);
System.out.println(subTour.toString());
}
if (subTourPool.size() == 1) {
System.out.println("end");
return true;
} else {
System.out.println("Left:" + subTourPool.size() + " subtours");
return false;
}
}
}
}
------------------------------
Jixuan Feng
------------------------------
#DecisionOptimization