[Help-glpk] Strange Question

[Welson Sun]

Hi all, I have met a strange question with Glpk, can you help me out?

 

I am using Glpk in Cygwin under WindowsXP. Since currently there is no Windows makefile for Glpk JNI, I used the precompiled version from address@hidden .

 

My LP problem is quite simple:

 

Minimize C1X1 + C2X2 + ..... + CnXn

So that

    Xi - Xj <= Wij ( 1 <= i,j <= n )

 

Where all X are integer and all Wij are non-negtive integer.

 

The first strange problem is that I can use simplex() method to solve this, while I cannot use integer() method to solve this, the later will report:

 

GlpkMsg: lpx_integer: optimal solution of LP relaxation required

 

I have set the problem to be MIP type, so how can this be possible?

 

 

The second strange problem is that I cannot retrieve the X solution correctly when the number of X is greater than 40. It will solve the problem, I have tested with 1000 X variables, but it just cannot retrieve the solution, sometimes it will report:

ufree: ptr = 0095CB90; memory allocation error

And sometimes, it just exits when it is in the middle of retriving solution.

 

Here is the main code:

 

public ArrayList minLoopCut(DirectedGraph g){

 

  // Create the LP problem object, set its name and optimization
  //   direction and some housekeeping routines
  GlpkSolver solver;
  try {
   solver = new GlpkSolver();
  } catch (Error e) {
   System.err.println("Can't instantiate solver:");
   return null;
  }

 

  // Since we've hooked the messages we don't need stdout/err printing
        solver.setHook(this);
  solver.enablePrints(false);

 

        // Set general things
  solver.setClss(GlpkSolver.LPX_MIP);
        solver.setObjDir(GlpkSolver.LPX_MIN);
       
        int nodeCount = g.nodeCount();

 

        // Set the column variable number, i.e. number of nodes
        solver.addCols(nodeCount);

 

        // For each column variable, set its name, bound and target
        // coefficient value
        // If a node has no input or output, its retiming value = 0,
        // else, its retiming value is free
        // The coefficient is the indegree - outdegree
        for (int i=1; i<=nodeCount; i++){
            solver.setColKind(i, GlpkSolver.LPX_IV);

 

            int inDegree = g.inputEdgeCount(g.node(i-1));
            int outDegree = g.outputEdgeCount(g.node(i-1));

 

            if ( inDegree == 0 || outDegree == 0 )
                solver.setColBnds(i, GlpkSolver.LPX_FX, 0.0, 0.0);
            else
                solver.setColBnds(i, GlpkSolver.LPX_FR, 0.0, 0.0);

 

            solver.setColCoef(i, inDegree - outDegree);
        }

 

        // Set the row variable number, i.e. number of edges
        int edgeCount = g.edgeCount();
        solver.addRows(edgeCount);
       
        // Prepare the constraint matrix row and column index array, and
        // corresponding value
        // array size = 2 * number of rows + 1
        int arraySize = edgeCount * 2 + 1;
        int ia[] = new int[arraySize]; //row index array
        int ja[] = new int[arraySize]; //column index array
        double ar[] = new double[arraySize]; //arry value 
       

 

        // For each row variable, set its bound (i.e. Wij's bound)
        // Ri - Rj < Wij
        for (int row=1; row<=edgeCount; row++){
           
            Edge edge = g.edge(row-1);
            int regCount = edgeRegArray[g.edgeLabel(edge)];

 

            solver.setRowBnds(row, GlpkSolver.LPX_UP, 0.0, regCount);

 

            int row_index = row * 2 -1;
            ia[row_index] = row;
            ja[row_index] = g.nodeLabel(edge.source()) + 1;
            ar[row_index] = 1.0;

 

            row_index = row * 2;
            ia[row_index] = row;
            ja[row_index] = g.nodeLabel(edge.sink()) + 1;
            ar[row_index] = -1.0;
        }

 

        // Load matrix
        solver.loadMat3( 2 * edgeCount, ia, ja, ar);
       
        // Solve it
        int res = solver.simplex();
   if (res != GlpkSolver.LPX_E_OK ||
    (solver.getStatus() != GlpkSolver.LPX_OPT &&
     solver.getStatus() != GlpkSolver.LPX_FEAS)) {
    System.err.println("Sample: simplex() failed");
    return null;
   }
       
        // Recalculating the edge weight
        int finalCutNumber = 0;
       
       
        GlpkSolverInfo sourceR = new GlpkSolverInfo();
        GlpkSolverInfo sinkR = new GlpkSolverInfo();
        for(int i=0; i<edgeCount; i++){
            Edge edge = g.edge(i);
            int edgeIndex = g.edgeLabel(edge);
            int regCount = edgeRegArray[edgeIndex];
           
            int source = g.nodeLabel(edge.source()) + 1;
            solver.getColInfo(source, sourceR);

 

            int sink = g.nodeLabel(edge.sink()) + 1;
            solver.getColInfo(sink, sinkR);
           
            int newRegCount = regCount + (int)sinkR.vx - (int)sourceR.vx;
           
//             double source = solver.getMIPCol( g.nodeLabel(edge.source()) + 1);
//             double sink =   solver.getMIPCol( g.nodeLabel(edge.sink()) + 1 );
//             int newRegCount = regCount + (int)sink - (int)source;

 

            edgeRegArray[edgeIndex] = newRegCount;
           
            if (newRegCount != 0) {
                finalCutNumber ++;
            }
        }
       
        System.out.println("Final cut number: " + finalCutNumber);
        return null;
    }