[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Strange Question
From: |
Welson Sun |
Subject: |
[Help-glpk] Strange Question |
Date: |
Tue, 2 Mar 2004 16:10:19 -0700 |
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;
}
- [Help-glpk] Strange Question,
Welson Sun <=