Re: Requesting help regarding running LPSOLVE-MATLAB on windows xp64

Dear all

 

I developed a model to solve a MIP problem envolving resource alocation for some demands. It's simple, but with a large number of variables. Well, analysing some results, i found a apparent problem with some binary variables used with real variables in certain constraints. It seems that in some cases the result don't "respect" constraints, but lp-solve shows "optimal solution" found. I reduce the model to show you the question:

 

###### (1) Original model:

 

/* Objective function */
min: +8.01 R1 +16.09 R2;

/* Constraints */
UNIQUE: +B1 +B2 = 1;
RESOURCE_1: +1000000 B1 -R1 >= 0;
RESOURCE_2: +1000000 B2 -R2 >= 0;
DISPONIBILITY: +R1 +R2 <= 1;
DEMAND: +184 R1 +368 R2 >= 193;

/* Variable bounds */
B1 <= 1;
B2 <= 1;

/* Integer definitions */
int B1,B2;

 

Explaining: I have two binary variables [B1,B2] but accept only one with value [1] as result. The other will set to zero [0]. The real variable [R1,R2] are associated with binary variables [B1,B2]. So, R1 can be non zero only in case B1 is non zero. On other way, R2 can be non zero only in case B2 is non zero. So i expected that if R1 is non zero, R2 is zero. Or if R2 is non zero, R1 must be zero. But when we process this model in lp-solve (using IDE, for example), we receive the result:

 

B1: 1

B2: 0

R1: 0.9510869...

R2: 0.0489130...  => Here is the problem !!! How can this occurs if [B2 = 0] AND [+1000000 B2 -R2 >= 0] ???

 

After that i made two simple changes in model, and receive&nbsp;"correct" results:

 

##### (2) Alternative model 1:

 

/* Objective function */
min: +8 R1 +16 R2; &nbsp;   /* HERE CHANGE TO INTEGER VALUES */

/* Constraints */
UNIQUE: +B1 +B2 = 1;
RESOURCE_1: +1000000 B1 -R1 >= 0;
RESOURCE_2: +1000000 B2 -R2 >= 0;
DISPONIBILITY: +R1 +R2 <= 1;
DEMAND: +184 R1 +368 R2 >= 193;

/* Variable bounds */
B1 <= 1;
B2 <= 1;

/* Integer definitions */
int B1,B2;

 

If we change original objective funtion to use integer constants, model runs "ok&quot;, givin:

 

B1: 0

B2: 1

R1: 0

R2: 0.5244565

 

##### (3) Alternative model 1:

 

/* Objective function */
min: +8.01 R1 +16.09 R2;

/* Constraints */
UNIQUE: +B1 +B2 = 1;
RESOURCE_1: +100000 B1 -R1 >= 0; &nbsp; /* HERE REDUCE CONSTANT FROM 1,000,000 to 100,000 */
RESOURCE_2: +100000 B2 -R2 >= 0; &nbsp; /* HERE REDUCE CONSTANT FROM 1,000,000 to 100,000 */
DISPONIBILITY: +R1 +R2 <= 1;
DEMAND: +184 R1 +368 R2 >= 193;

/* Variable bounds */
B1 <= 1;
B2 <= 1;

/* Integer definitions */
int B1,B2;

 

In this case, if we change coeficients from [B1,B2] from 1,000,000 to 100,000, it gives correct result too:

 

B1: 0

B2: 1

R1: 0

R2: 0.5244565

 

There is some instability in models that mix binary and real variables with large (?) coeficients ? If someone knows what is happened here, please tell me what to do. Maybe it's some parameter or limit to set.... but i don't see now how to understand the origin of the problem.

 

PS: I'm using lp-solve version 5.5.0.10.

 

Thanks a lot

 

Alexandre Fernandes de Alencar
Ribeirão Preto - Brazil
e-mail: alexandreilab.com.br" target="_blank">alexandreilab.com.br

Peter

 

Thanks for your explanation. In that case, i really reduce my "BigM' value to 1000 in order to solve my problem.

 

But, the sample i post is really a simplification for the question. In some cases, i must have a value for BigM greater than 100.000, in order to treat the real problem.

For example, if [Rn] represent possibles ensures for diferent investiments. In this case, possible values for any [Rn] can be bigger than 1.000.000 ($).

 

If we have this situation, what is a possible strategy to treat this question ? Maybe use a "alternative" scale for values, dividing every value ;by a common factor (p.e: /1000) ?

 

Thanks

 &nbsp; 
Alexandre Fernandes de Alencar
Ribeirão Preto - Brazil

e-mail: alexandreilab.com.br" target="_blank">alexandreilab.com.br

----- Original Message -----

From: telenet.be" href="mailto:_peno_telenet.be" target="_blank">Peter Notebaert

To: lp_solveyahoogroups.com

Sent: Thursday, June 12, 2008 12:11 PM

Subject: Re: [lp_solve] Strange behaviour in MIP Problem

1000000 Is too big and gives instabilities. You must use more realistic values for you 'BigM' values. Those big values can give rounding errors that result in a solution that can be numerical unstable and/or not within the set constraints.

For example in this case you know from the constraint +R1 + R2 <= 1 that R1 and R2 cannot be larger than 1, so the coefficients of B1 and B2 don't have to be larger than 1 also!

 

As I already said in previous post, they should disallow to use the term BigM for those coefficients because people then tend to use too big variables.

 

Peter

On Thu, Jun 12, 2008 at 4:04 PM, Alexandre Fernandes de Alencar < alexandreilab.com.br" target="_blank">alexandreilab.com.br> wrote:

Dear all

 

I developed a model to solve a MIP problem envolving resource alocation for some demands. It's simple, but with a large number of variables. Well, analysing some results,&nbsp;i found a apparent problem with some binary variables used with real variables in certain constraints. It seems that in some cases the result don't "respect"&nbsp;constraints, but lp-solve shows "optimal solution" found. I reduce the model to show you the question:

 

###### (1) Original model:

 

/* Objective function */
min: +8.01 R1 +16.09 R2;

/* Constraints */
UNIQUE: +B1 +B2 = 1;
RESOURCE_1: +1000000 B1 -R1 >= 0;
RESOURCE_2: +1000000 B2 -R2 >= 0;
DISPONIBILITY: +R1 +R2 <= 1;
DEMAND: +184 R1 +368 R2 >= 193;

/* Variable bounds */
B1 <= 1;
B2 <= 1;

/* Integer definitions */
int B1,B2;

 

Explaining: I have two binary variables [B1,B2] but accept only one with value [1] as result. The other will set to zero [0]. The real variable [R1,R2] are associated with binary variables [B1,B2]. So, R1 can be non zero only in case B1 is non zero. On other way, R2 can be non zero only in case B2 is non zero. So i expected that if R1 is non zero, R2 is zero. Or if R2 is non zero, R1 must be zero. But when we process this model in lp-solve (using IDE, for example), we receive the result:

 

B1: 1

B2: 0

R1: 0.9510869...

R2: 0.0489130...  => Here is the problem !!! How can this occurs if [B2 = 0] AND [+1000000 B2 -R2 >= 0] ???

 

After that i made two simple changes in model, and receive&nbsp;"correct" results:

 

##### (2) Alternative model 1:

 

/* Objective function */
min: +8 R1 +16 R2; &nbsp;   /* HERE CHANGE TO INTEGER VALUES */

/* Constraints */
UNIQUE: +B1 +B2 = 1;
RESOURCE_1: +1000000 B1 -R1 >= 0;
RESOURCE_2: +1000000 B2 -R2 >= 0;
DISPONIBILITY: +R1 +R2 <= 1;
DEMAND: +184 R1 +368 R2 >= 193;

/* Variable bounds */
B1 <= 1;
B2 <= 1;

/* Integer definitions */
int B1,B2;

 

If we change original objective funtion to use integer constants, model runs "ok", givin:

 

B1: 0

B2: 1

R1: 0

R2: 0.5244565

 

##### (3) Alternative model 1:

 

/* Objective function */
min: +8.01 R1 +16.09 R2;

/* Constraints */
UNIQUE: +B1 +B2 = 1;
RESOURCE_1: +100000 B1 -R1 >= 0; &nbsp; /* HERE REDUCE CONSTANT FROM 1,000,000 to 100,000 */
RESOURCE_2: +100000 B2 -R2 >= 0; &nbsp; /* HERE REDUCE CONSTANT FROM 1,000,000 to 100,000 */
DISPONIBILITY: +R1 +R2 <= 1;
DEMAND: +184 R1 +368 R2 >= 193;

/* Variable bounds */
B1 <= 1;
B2 <= 1;

/* Integer definitions */
int B1,B2;

 

In this case, if we change coeficients from [B1,B2] from 1,000,000 to 100,000, it gives correct result too:

 

B1: 0

B2: 1

R1: 0

R2: 0.5244565

 

There is some instability in models that mix binary and real variables with large (?) coeficients ? If someone knows what is happened here, please tell me what to do. Maybe it's some parameter or limit to set.... but i don't see now how to understand the origin of the problem.

 

PS: I'm using lp-solve version 5.5.0.10.

 

Thanks a lot

 

Alexandre Fernandes de Alencar
Ribeirão Preto - Brazil
e-mail: alexandreilab.com.br" target="_blank">alexandreilab.com.br