[Help-glpk] Feed GLPK with feasible initial solution?

help-glpk

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] Feed GLPK with feasible initial solution?

From:	Lauro Lins
Subject:	[Help-glpk] Feed GLPK with feasible initial solution?
Date:	Tue, 25 Sep 2007 09:44:03 +0400

Hi,
I have a MIP Problem which I can provide feasible solutions very easily.
How can I feed the GLPK MIP Solver with a feasible solution, to help him.
Running the solver without any help it takes a lot of time and can #39;t get
even a feasible solution. Do you have a small example of this?
Thanks.
Lauro Lins
address@hidden

P.S
. An instance of my model is this one:




/* conjunto de a??es aDi = a??o desacoplar gaiola i, aSi = substituir gaiola i, 
aAi = acoplar gaiola i */
set A;

/* conjunto de equipes */
set E;

/* conjunto de dependencias do tipo acao 1 vem depois de acao 2 */
set R within {a1 in A, a2 in A: a1 <> a2};

/* atribui??o das equipes */
set A2E within {A,E};

/* tempo para realizar a??o */
param aindex{A};

/* pares de a??o da mesma equipe */
set AAE := setof {(a1,e) in A2E, (a2,e) in A2E: a1 <> a2 and aindex[a1] < 
aindex[a2]} (a1,a2);

/* tempo para realizar a??o */
param atime{a in A};

/* tempo entre a??es */
param aatime{a1 in A, a2 in A};

/* starting time of the actions */
var x{A};

/* starting time of the actions */
var y{A};

/* starting time of the actions */
var z;

/* integral contraint */
var i{AAE}, binary;

/**************************/
/* INICIALIZAR PARAMETROS */
/**************************/

/* total transportation costs in thousands of dollars */
/* minimize cost: 1E+2 * z + 1E-1 * sum{a in A} y[a]; */
minimize cost: z;

/* total transportation costs in thousands of dollars */
s.t. R0{a in A}: x[a] >= 0;

/* total transportation costs in thousands of dollars */
s.t. R1{a in A}: y[a] = x[a] + atime[a];

/* z is greater than y[a] */
s.t. R2{a in A}: z >= y[a];

/* dependencias antes-depois */
s.t. R3{(a1,a2) in R}: y[a1] <= x[a2];

/* dependencias de atividades da mesma equipe */
s.t. R4{(a1,a2) in AAE}: y[a1] + aatime[a1,a2] - x[a2] <= 1E+3 * i[a1,a2];
s.t. R5{(a1,a2) in AAE}: y[a2] + aatime[a2,a1] - x[a1] <= 1E+3 * (1- i[a1,a2]);

/**************************/
/* INICIALIZAR PARAMETROS */
/**************************/
data;

/* conjunto de a??es aDi = a??o desacoplar gaiola i, aSi = substituir gaiola i, 
aAi = acoplar gaiola i */
set A := aD1 aS1 aA1 aD2 aS2 aA2 aD3 aS3 aA3 aS1c1 aD1c1 aA1c1 aD1c2 aS1c2 
aA1c2 aD2c1 aS2c1 aA2c1 aD3c1 aS3c1 aA3c1 ;

param aindex:= aD1 1 aS1 2 aA1 3 aD2 4 aS2 5 aA2 6 aD3 7 aS3 8 aA3 9 aS1c1 10 
aD1c1 11 aA1c1 12 aD1c2 13 aS1c2 14 aA1c2 15 aD2c1 16 aS2c1 17 aA2c1 18 aD3c1 
19 aS3c1 20 aA3c1 21 ;

/* conjunto de equipes: eP = equipe da ponte, eDA = equipe desacoplar acoplar */
set E := eP eDA ;

/* pares de a??es que tem que vir uma antes da outra */
set R := (aD1,aS1) (aS1,aA1) (aD2,aS2) (aS2,aA2) (aD3,aS3) (aS3,aA3) 
(aD1c2,aS1c2) (aS1c2,aA1c2) (aD2c1,aS2c1) (aS2c1,aA2c1) (aD3c1,aS3c1) 
(aS3c1,aA3c1) ;

/* equipe das a??es */
set A2E := (aD1,eDA) (aS1,eP) (aA1,eDA) (aD2,eDA) (aS2,eP) (aA2,eDA) (aD3,eDA) 
(aS3,eP) (aA3,eDA) (aS1c1,eP) (aD1c1,eDA) (aA1c1,eDA) (aD1c2,eDA) (aS1c2,eP) 
(aA1c2,eDA) (aD2c1,eDA) (aS2c1,eP) (aA2c1,eDA) (aD3c1,eDA) (aS3c1,eP) 
(aA3c1,eDA) ;

/* tempo interno as a??es em minutos */
param atime := aD1 5.0 aS1 2.3333333333333335 aA1 5.0 aD2 5.0 aS2 
2.3333333333333335 aA2 5.0 aD3 5.0 aS3 2.3333333333333335 aA3 5.0 aS1c1 
2.3333333333333335 aD1c1 5.0 aA1c1 
5.0 aD1c2 5.0 aS1c2 2.3333333333333335 aA1c2 5.0 aD2c1 5.0 aS2c1 
2.3333333333333335 aA2c1 5.0 aD3c1 5.0 aS3c1 2.3333333333333335 aA3c1 5.0 ;

/* tempo interno as a??es em minutos */
param aatime : aD1 aS1 aA1 aD2 aS2 aA2 aD3 aS3 aA3 aS1c1 aD1c1 aA1c1 aD1c2 
aS1c2 aA1c2 aD2c1 aS2c1 aA2c1 aD3c1 aS3c1 aA3c1  :=
aD1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 
0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 
0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 
aS1 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 
aA1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334
 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 
0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 
aD2 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 
0.0 0.02666666666666667 0.0 0.02666666666666667 0.02666666666666667 
0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 
0.02666666666666667 
aS2 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 0.13333333333333333
 0.0 0.13333333333333333 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 
0.13333333333333333 0.0 
aA2 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 
0.0 0.02666666666666667 0.0 0.02666666666666667
 0.02666666666666667 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 
0.02666666666666667 0.0 0.02666666666666667 
aD3 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 
0.02666666666666667 0.0 
0.0 0.0 0.0 0.05333333333333334 0.05333333333333334 0.05333333333333334 0.0 
0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 
aS3 0.0 0.26666666666666666 0.0 0.0 0.13333333333333333 0.0 0.0 0.0
 0.0 0.26666666666666666 0.0 0.0 0.0 0.26666666666666666 0.0 0.0 
0.13333333333333333 0.0 0.0 0.0 0.0 
aA3 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 
0.02666666666666667 0.0 0.0 0.0 0.0 0.05333333333333334
 0.05333333333333334 0.05333333333333334 0.0 0.05333333333333334 
0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 
aS1c1 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 0.0 
0.0 0.0 0.0 0.0 0.0
 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 
aD1c1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 
0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 
0.02666666666666667 0.0 0.02666666666666667
 0.05333333333333334 0.0 0.05333333333333334 
aA1c1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 
0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 
0.02666666666666667 0.0 0.02666666666666667
 0.05333333333333334 0.0 0.05333333333333334 
aD1c2 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 
0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 
0.02666666666666667 0.0 0.02666666666666667
 0.05333333333333334 0.0 0.05333333333333334 
aS1c2 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 0.0 
0.0 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 
aA1c2 0.0 0.0 
0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 
0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 
0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 
aD2c1 0.02666666666666667
 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 
0.02666666666666667 0.0 0.02666666666666667 0.02666666666666667 
0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 
0.02666666666666667 
aS2c1 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 
0.13333333333333333 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 
0.13333333333333333 0.0 
aA2c1 0.02666666666666667 0.0 0.02666666666666667
 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.0 
0.02666666666666667 0.02666666666666667 0.02666666666666667 0.0 
0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 
aD3c1 0.05333333333333334
 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 
0.0 0.0 0.05333333333333334 0.05333333333333334 0.05333333333333334 0.0 
0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 
0.0 
aS3c1 0.0 0.26666666666666666 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 
0.26666666666666666 0.0 0.0 0.0 0.26666666666666666 0.0 0.0 0.13333333333333333 
0.0 0.0 0.0 0.0 
aA3c1 0.05333333333333334 0.0 0.05333333333333334
 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.0 
0.05333333333333334 0.05333333333333334 0.05333333333333334 0.0 
0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 
;

end;

Hi,
I have a MIP Problem which I can provide feasible solutions very easily.
How can I feed the GLPK MIP Solver with a feasible solution, to help him.
Running the solver without any help it takes a lot of time and can't get
even a feasible solution. Do you have a small example of this?
Thanks.
Lauro Lins
address@hidden

P.S . An instance of my model is this one:

/* conjunto de a??es aDi = a??o desacoplar gaiola i, aSi = substituir gaiola i, aAi = acoplar gaiola i */
set A;

/* conjunto de equipes */
set E;

/* conjunto de dependencias do tipo acao 1 vem depois de acao 2 */
set R within {a1 in A, a2 in A: a1 <> a2};

/* atribui??o das equipes */
set A2E within {A,E};

/* tempo para realizar a??o */
param aindex{A};

/* pares de a??o da mesma equipe */
set AAE := setof {(a1,e) in A2E, (a2,e) in A2E: a1 <> a2 and aindex[a1] < aindex[a2]} (a1,a2);

/* tempo para realizar a??o */
param atime{a in A};

/* tempo entre a??es */
param aatime{a1 in A, a2 in A};

/* starting time of the actions */
var x{A};

/* starting time of the actions */
var y{A};

/* starting time of the actions */
var z;

/* integral contraint */
var i{AAE}, binary;

/**************************/
/* INICIALIZAR PARAMETROS */
/**************************/

/* total transportation costs in thousands of dollars */
/* minimize cost: 1E+2 * z + 1E-1 * sum{a in A} y[a]; */
minimize cost: z;

/* total transportation costs in thousands of dollars */
s.t. R0{a in A}: x[a] >= 0;

/* total transportation costs in thousands of dollars */
s.t. R1{a in A}: y[a] = x[a] + atime[a];

/* z is greater than y[a] */
s.t. R2{a in A}: z >= y[a];

/* dependencias antes-depois */
s.t. R3{(a1,a2) in R}: y[a1] <= x[a2];

/* dependencias de atividades da mesma equipe */
s.t. R4{(a1,a2) in AAE}: y[a1] + aatime[a1,a2] - x[a2] <= 1E+3 * i[a1,a2];
s.t. R5{(a1,a2) in AAE}: y[a2] + aatime[a2,a1] - x[a1] <= 1E+3 * (1- i[a1,a2]);

/**************************/
/* INICIALIZAR PARAMETROS */
/**************************/
data;

/* conjunto de a??es aDi = a??o desacoplar gaiola i, aSi = substituir gaiola i, aAi = acoplar gaiola i */
set A := aD1 aS1 aA1 aD2 aS2 aA2 aD3 aS3 aA3 aS1c1 aD1c1 aA1c1 aD1c2 aS1c2 aA1c2 aD2c1 aS2c1 aA2c1 aD3c1 aS3c1 aA3c1 ;

param aindex:= aD1 1 aS1 2 aA1 3 aD2 4 aS2 5 aA2 6 aD3 7 aS3 8 aA3 9 aS1c1 10 aD1c1 11 aA1c1 12 aD1c2 13 aS1c2 14 aA1c2 15 aD2c1 16 aS2c1 17 aA2c1 18 aD3c1 19 aS3c1 20 aA3c1 21 ;

/* conjunto de equipes: eP = equipe da ponte, eDA = equipe desacoplar acoplar */
set E := eP eDA ;

/* pares de a??es que tem que vir uma antes da outra */
set R := (aD1,aS1) (aS1,aA1) (aD2,aS2) (aS2,aA2) (aD3,aS3) (aS3,aA3) (aD1c2,aS1c2) (aS1c2,aA1c2) (aD2c1,aS2c1) (aS2c1,aA2c1) (aD3c1,aS3c1) (aS3c1,aA3c1) ;

/* equipe das a??es */
set A2E := (aD1,eDA) (aS1,eP) (aA1,eDA) (aD2,eDA) (aS2,eP) (aA2,eDA) (aD3,eDA) (aS3,eP) (aA3,eDA) (aS1c1,eP) (aD1c1,eDA) (aA1c1,eDA) (aD1c2,eDA) (aS1c2,eP) (aA1c2,eDA) (aD2c1,eDA) (aS2c1,eP) (aA2c1,eDA) (aD3c1,eDA) (aS3c1,eP) (aA3c1,eDA) ;

/* tempo interno as a??es em minutos */
param atime := aD1 5.0 aS1 2.3333333333333335 aA1 5.0 aD2 5.0 aS2 2.3333333333333335 aA2 5.0 aD3 5.0 aS3 2.3333333333333335 aA3 5.0 aS1c1 2.3333333333333335 aD1c1 5.0 aA1c1 5.0 aD1c2 5.0 aS1c2 2.3333333333333335 aA1c2 5.0 aD2c1 5.0 aS2c1 2.3333333333333335 aA2c1 5.0 aD3c1 5.0 aS3c1 2.3333333333333335 aA3c1 5.0 ;

/* tempo interno as a??es em minutos */
param aatime : aD1 aS1 aA1 aD2 aS2 aA2 aD3 aS3 aA3 aS1c1 aD1c1 aA1c1 aD1c2 aS1c2 aA1c2 aD2c1 aS2c1 aA2c1 aD3c1 aS3c1 aA3c1 :=
aD1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334
aS1 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0
aA1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334
aD2 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.0 0.02666666666666667 0.02666666666666667 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667
aS2 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.13333333333333333 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0
aA2 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.0 0.02666666666666667 0.02666666666666667 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667
aD3 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.0 0.05333333333333334 0.05333333333333334 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0
aS3 0.0 0.26666666666666666 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.26666666666666666 0.0 0.0 0.0 0.26666666666666666 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0
aA3 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.0 0.05333333333333334 0.05333333333333334 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0
aS1c1 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0
aD1c1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334
aA1c1 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334
aD1c2 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334
aS1c2 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.26666666666666666 0.0
aA1c2 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334 0.0 0.0 0.0 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.05333333333333334 0.0 0.05333333333333334
aD2c1 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.0 0.02666666666666667 0.02666666666666667 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667
aS2c1 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0 0.13333333333333333 0.0 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.0 0.13333333333333333 0.0
aA2c1 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667 0.0 0.02666666666666667 0.02666666666666667 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.02666666666666667 0.0 0.02666666666666667
aD3c1 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.0 0.05333333333333334 0.05333333333333334 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0
aS3c1 0.0 0.26666666666666666 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0 0.26666666666666666 0.0 0.0 0.0 0.26666666666666666 0.0 0.0 0.13333333333333333 0.0 0.0 0.0 0.0
aA3c1 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0 0.0 0.05333333333333334 0.05333333333333334 0.05333333333333334 0.0 0.05333333333333334 0.02666666666666667 0.0 0.02666666666666667 0.0 0.0 0.0
;

end;

[Prev in Thread]

Current Thread

[Next in Thread]

[Help-glpk] Feed GLPK with feasible initial solution?, Lauro Lins <=
- Re: [Help-glpk] Feed GLPK with feasible initial solution?, Andrew Makhorin, 2007/09/25

Prev by Date: Re: [Help-glpk] Problem infeasibility
Next by Date: Re: [Help-glpk] Problem infeasibility
Previous by thread: [Help-glpk] Problem infeasibility
Next by thread: Re: [Help-glpk] Feed GLPK with feasible initial solution?
Index(es):
- Date
- Thread