Originally posted by: Bicycle
Hi all,
as a part of my final thesis I am implementing a column generation algorithm in Java (Eclipse). In order to solve the LPs I integrated Cplex. The problem is as follows:
My CG Algorithm starts with a unity matrix, so every column is chosen once in the first RMP. The Duals are generated and the subproblem (maximal stable set) is called, but the duals are wrong, I always get at least the first generated column twice.
I think that it is not a problem of Cplex but a problem of my implementation.
I implemented a minimal example so that you can comprehend the problem and probably give me hints.
I would be very thankful if some finds my mistakes, I've been searching for a solution for about 2 weeks now.
Greetings
public class ColumnGeneration {
private int[] jobs;
private int[][] conflicts;
private int[][] columns;
private int[][] helpcolumns;
private double ub;
private double lb;
private double maxC;
private double[] duals;
public ColumnGeneration(int[] newjobs, int[][] newconflicts, double newub, double newlb) {
jobs = newjobs;
conflicts = newconflicts;
ub = newub;
lb = newlb;
}
public void ColGenStart(){
maxC = Math.floor((ub+lb)*0.5);
//unity matrix
columns = new int[jobs.length][jobs.length];
for(int i = 0; i<jobs.length; i++){
columns[i][i] = 1;
}
MasterProblem();
}
public void MasterProblem(){
//Print the Matrix
System.out.println();
for(int i=0; i<columns.length; i++){
for(int j=0; j<columns[0].length; j++){
System.out.print(columns[i][j]+" ");
}
System.out.println();
}
System.out.println();
//CPLEX Parameter
int j = columns.length;
int c = columns[0].length;
try{
//newModel
IloCplex cplex = new IloCplex();
//variables
IloNumVar[] x = new IloNumVar[c];
for(int i=0; i<c; i++){
x[i] = cplex.numVar(0, 1);
}
//expressions
IloLinearNumExpr[] Nebenbed = new IloLinearNumExpr[j];
for(int i=0; i<j; i++){
Nebenbed[i] = cplex.linearNumExpr();
for(int k=0; k<c; k++){
Nebenbed[i].addTerm(columns[i][k], x[k]);
}
}
IloLinearNumExpr objective = cplex.linearNumExpr();
for(int l=0; l<c; l++){
objective.addTerm(1, x[l]);
}
//define objective
cplex.addMinimize(objective);
//constraints
List<IloRange> constraints = new ArrayList<IloRange>();
for(int l=0; l<j; l++){
constraints.add(l, cplex.addGe(Nebenbed[l], 1));
}
if(cplex.solve()){
//Print ObjValue and Variables
System.out.println();
System.out.println("ObjValue is "+cplex.getObjValue());
System.out.println();
System.out.println("Variables are: ");
for(int i=0; i<c; i++){
System.out.print(cplex.getValue(x[i])+" ");
}
System.out.println();
//Generate Duals
duals = new double[c];
System.out.println();
System.out.println("Duals are: ");
for(int k=0; k<constraints.size(); k++){
duals[k] = cplex.getDual(constraints.get(k));
}
System.out.println();
for(int l=0; l<constraints.size();l++)
System.out.println("Dual "+(l+1)+" = "+cplex.getDual(constraints.get(l)));
System.out.println();
System.out.println();
System.out.println("Solve Subproblem:");
SubProblem();
}
else{
System.out.println("Model not solvable");
}
}
catch(IloException e){
e.printStackTrace();
}
}
public void SubProblem(){
//CPLEX Parameter
int j = columns.length;
System.out.println();
System.out.println();
System.out.println();
System.out.println();
try{
//newModel
IloCplex cplex = new IloCplex();
//variables
IloIntVar[] x = new IloIntVar[j];
for(int l=0; l<j; l++){
x[l] = cplex.intVar(0, 1);
}
IloNumVar y = cplex.numVar(0, Double.MAX_VALUE);
//expressions
IloLinearNumExpr Nebenbed = cplex.linearNumExpr();
for(int i=0; i<j; i++){
Nebenbed.addTerm(jobs[i], x[i]);
}
IloLinearNumExpr objective = cplex.linearNumExpr();
for(int l=0; l<j; l++){
objective.addTerm(duals[l], x[l]);
}
//define objective
cplex.addMaximize(objective);
//constraints
List<IloRange> constraints = new ArrayList<IloRange>();
constraints.add(cplex.addLe(Nebenbed, maxC));
cplex.addEq(Nebenbed, y);
for(int i=0; i<conflicts.length; i++){
for(j=i+1; j<conflicts.length; j++){
if(conflicts[i][j]==1){
constraints.add(cplex.addLe(cplex.sum(x[i], x[j]),1));
}
}
}
if(cplex.solve()){
System.out.println("New solution is found.");
//If new "better" column is found -> add
if(cplex.getObjValue()>1){
double[] newcolumn = new double[x.length];
for(int i=0; i<x.length; i++){
System.out.print(cplex.getValue(x[i])+" ");
newcolumn[i] = cplex.getValue(x[i]);
}
System.out.println("New Columns is found -> "+cplex.getObjValue());
//Add Column to matrix
helpcolumns = new int[columns.length][columns[0].length];
helpcolumns = columns;
columns = new int[helpcolumns.length][helpcolumns[0].length+1];
for(int i=0; i<helpcolumns.length; i++){
for(int k=0; k<helpcolumns[0].length; k++){
columns[i][k] = helpcolumns[i][k];
}
}
for(int i=0; i<columns.length; i++){
columns[i][helpcolumns[0].length] = (int)cplex.getValue(x[i]);
}
//Call MasterProblem
MasterProblem();
}
else{
System.out.println();
//FinalMasterProblem();
}
}
}
catch(IloException e){
e.printStackTrace();
}
}
public static void main(String args[]){
int[] newjobs = {18,25,22,21,2,13,9,17,25,19};
int newub = 100;
int newlb=0;
for(int i=0; i<newjobs.length; i++){
newlb += newjobs[i];
}
int[][] newconflicts = {{0,1,1,0,1,0,0,0,0,0},
{1,0,1,0,1,1,0,0,0,0},
{1,1,0,0,0,1,0,0,1,1},
{0,0,0,0,0,1,0,1,1,0},
{1,1,0,0,0,0,0,0,1,1},
{0,1,1,1,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0,0},
{0,0,1,1,1,0,0,0,0,0},
{0,0,1,0,1,0,0,0,0,0}};
ColumnGeneration Start = new ColumnGeneration(newjobs, newconflicts, newub, newlb);
Start.ColGenStart();
}
}
#CPLEXOptimizers#DecisionOptimization