Originally posted by: Trino

Hi, I'm using Concorde TSP (link) in my code and cplex as the LP solver under Ubuntu 13.10. To configure cplex to run with concorde I've followed this tutorial (link). 

This seemed to work just fine and the code was running, however when I was testing with some instances (more difficult ones) I started getting a segmentation error inside concorde. Then I used a tool called Valgrind to track memory issues and see where exactly this error was occurring.

By doing this I was able to track this error as in the following Valgrind partial log:

==9393== Invalid read of size 8
==9393==    at 0xA30FC1: _ce6007f7a0de6211bed50ce70507921e (in /home/user/Projects/)
==9393==    by 0x6AEB21: CPXgetweight (in /home/user/Projects/)
==9393==    by 0x1054A01: CClp_getweight (lpcplex8.c:1583)
==9393==    by 0x106F0E3: find_candidate_cliques.constprop.4 (branch.c:3080)
==9393==    by 0x107171C: CCtsp_find_branch_cliques (branch.c:2831)
==9393==    by 0x10725FD: CCtsp_find_branch (branch.c:414)
==9393==    by 0x1073CE9: CCtsp_bb_find_branch (branch.c:3746)
==9393==    by 0x1081106: do_task (bcontrol.c:1806)
==9393==    by 0x10816E3: bfs_process (bcontrol.c:511)
==9393==    by 0x1082C79: CCtsp_bfs_brancher (bcontrol.c:354)
==9393==    by 0x1021F5C: CCtsp_solve_dat (tsp_call.c:476)
==9393==    by 0x41CD0D: tspKnapsackBased(Instance*, int, int) (libAlgorithms.cpp:93)
==9393==  Address 0x6651100 is 0 bytes after a block of size 1,776 alloc'd
==9393==    at 0x4C2A2DB: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9393==    by 0xA5AC4B: _4c7a3f0a1aa7f72a2bf4bf50908012f8 (in /home/user/Projects/)
==9393==    by 0x6AEAFB: CPXgetweight (in /home/user/Projects/)
==9393==    by 0x1054A01: CClp_getweight (lpcplex8.c:1583)
==9393==    by 0x106F0E3: find_candidate_cliques.constprop.4 (branch.c:3080)
==9393==    by 0x107171C: CCtsp_find_branch_cliques (branch.c:2831)
==9393==    by 0x10725FD: CCtsp_find_branch (branch.c:414)
==9393==    by 0x1073CE9: CCtsp_bb_find_branch (branch.c:3746)
==9393==    by 0x1081106: do_task (bcontrol.c:1806)
==9393==    by 0x10816E3: bfs_process (bcontrol.c:511)
==9393==    by 0x1082C79: CCtsp_bfs_brancher (bcontrol.c:354)
==9393==    by 0x1021F5C: CCtsp_solve_dat (tsp_call.c:476)
==9393== 

So it seems that the error is generated when calling the cplex function CPXgetweight. The concorde function that calls CPXgetweight is the following:

int CClp_getweight (CClp *lp, int nrows, int *rmatbeg, int *rmatind,
                    double *rmatval, double *weight)
{
    int rval = 0;

#ifdef CC_ONE_ENV
    if (set_parameters (lp->cplex_env, &lp->cplex_params)) {
        fprintf (stderr, "Unable to set optimization parameters\n");
    }
#endif

    rval = CPXgetweight (lp->cplex_env, lp->cplex_lp, nrows,
                         rmatbeg, rmatind, rmatval, weight, CPX_DPRIIND_STEEP);
    if (rval) {
        fprintf (stderr, "CPXgetweight failed\n");
    }
    return rval;
}

I've been struggling with this problem for a couple of days now and I can't seem to find a solution. I'm not sure if I'm doing something wrong with the parameters for CCtsp_solve_dat or if it's a problem of incompatibility between concorde and cplex 12.5.1, which is the version that I'm using. Could anyone help me with this problem?

Ps: I've also attached the complete Concorde execution log (without Valgrind) up to the point of the error.

Thanks in advance. Any help is appreciated!

Originally posted by: BillCook

I don't know the problem with the CPX call, but you can avoid CPXgetweight by setting the longedge_branching parameter to 1 in the call to CCtsp_bfs_brancher () in the function tsp_solve_lp ().  So, on line 479 of file tsp_call () change the 0 to a 1.  I really should have set this to 1 in any case, since  longedge_branching is turned on by default in the main command-line call to concorde.  

Bill

Originally posted by: EdKlotz

I'm glad to see there's a way to work around the crash, as this may not be easy to quickly track down.   This crash could come from a problem in the code that calls Concorde, Concorde code, or CPLEX code.   The valgrind output indicates an invalid read of an array allocated by CPXgetweight or one of its child routines.  That could happen if any of the rmat* arguments passed to CPXgetweight contain invalid values (e.g. rmatind contains duplicate column indices, or a column index that exceeds the number of variables in the model associated with the CPXLP pointer), or (less likely) the rcnt value is too big.   Here are a few of tactics that might help track this down.

1)   CPLEX has a check.c file that you can compile and link into the application.   This contains some diagnostic routines that take the same arguments as the core model building and modifying routines, and run some checks on the arguments passed in.   While it doesn't contain any diagnostic routines for CPXgetweight, you can try calling CPXcheckaddrows instead, passing it in the rmat* arrays provided to the CPXgetweight function.   You'll have to add some other arguments to CPXcheckaddrows, by they mostly can be NULL or 0.   If the problem  involves invalid values in the rmat* arrays passed to CPXgetweight, this routine will probably identify the source of the trouble.

2)  At the point of the CPXgetweight call, try exporting the associated LP pointer to a SAV file.   Read the SAV file into interactive CPLEX with the datacheck parameter enabled.  That should verify that the problem data in the LP pointer is not corrupted in some way.

3)  With the SAV file from 2), modify the lpex2.c example program so that, after reading in the SAV file and solving, it calls  CPXgetweight with the same array values as in the Concorde call.   This will probably require dumping the CPXgetweight arguments in the problematic call from within Concorde to a binary file, then reading them back in to the small sample program.   Or, you could just pass them into to a subroutine that is essentially the lpex2.c example, but it also receives the CPXgetweight arguments and calls the CPXgetweight function.  If the problem can be reproduce in this simpler setup, that may make the problem easier to isolate and resolve.

Originally posted by: Trino

Thank you very much for the replies @BillCook and @EdKlotz. I tried the workaround proposed by Bill and it worked just fine, I'm not getting anymore that segmentation fault error. However I would like to try finding out why that error was happening.

Before trying what EdKlotz suggested I want to check whether or not the problem is in my code that calls concorde and see if I'm doing something wrong with the parameter values that I use to call CCtsp_solve_dat

The CCtsp_solve_dat function has the following prototype

int CCtsp_solve_dat (int ncount, CCdatagroup *indat, int *in_tour,
        int *out_tour, double *in_val, double *optval, int *success,
        int *foundtour, char *name, double *timebound, int *hit_timebound,
        int silent, CCrandstate *rstate)

In order to fill in an instance of CCdatagroup I first create the array of edges with size equal to the total number of edges*2, where the first edge connects the vertices in indexes 0 and 1, the second connects 2 and 3 and so on. I also create the array for the weights of each edge with total size equal to the number of edges and since my original weight values are double I multiply them by a scale factor of 1e3. Then I have the following code to create and fill the CCdatagroup instance:

CCdatagroup dataGroup;
CCutil_init_datagroup(&dataGroup);

CCutil_graph2dat_matrix(numVertices, numEdges, edgesC, edgesValuesC, INT_MAX, &dataGroup);

After this point I define and initialize the other variables needed to call CCtsp_solve_dat

int  *solutionTour = new int[numVertices]
    ,success = INT_MAX
    ,foundTour = INT_MAX
    ,hitTimeBound = INT_MAX
    ,concordeSeed = (int)CCutil_real_zeit();

double optVal = INT_MAX;

CCrandstate rstate;
CCutil_sprand (concordeSeed, &rstate);

Then I finally call CCtsp_solve_dat by doing

CCtsp_solve_dat(numVertices, &dataGroup, NULL, solutionTour, NULL, &optVal, &success, &foundTour, NULL, NULL, &hitTimeBound, false, &rstate);

Am I missing something or doing something wrong?

Thank you.

Bruno.

Originally posted by: Mimmo88

Concorde does not support CPLEX 12.5. I have downloaded QSopt and launched "./configure --with-qsopt=DIR" (DIR is the path where you find qsopt.a and qsopt.h). You have to load qsopt.a in your project.

I think this is your problem.

Domenico