Re: [Help-glpk] I got a solution that violates the constraints

[glpk xypron]

Hello Xiaomi,

> The value range is the problem I don't know. So far, the benchmark gives 
> the result that value ranges from 0 to 2000. However, the value may 
> increase in larger benchmark.

to avoid rounding problems you should reduce your "M" to the smallest
possible number.

E.g. if you had a problem like

var Xmax{j in J}, >= 0, <= ub[j];
var B{J}, binary; 
s.t. c1 {i in I} :
  sum{j in J} a[i,j] * Xmax[j] >= 1;
s.t. c2 {j in J} :
  Xmax[j] <= M * B[j];

you could write instead

var Xmax{j in J}, >= 0, <= ub[j];
var B{J}, binary; 
s.t. c1 {i in I} :
  sum{j in J} a[i,j] * Xmax[j] >= 1;
s.t. c2 {j in J} :
  Xmax[j] <= B[j]
  * max{i in I : a[i,j] > 0} ( if a[i,j] < 1 / ub[j] then ub[j] else 1 / 
a[i,j]);

> 
> By the way, is it the only way to formulate the total number of non-zero 
> value among all Xmax***_*** by following constrants:
> 
> 0<= Xmax***_*** <= M B,
> where M is a large number( I used 999,999 in my case), and B is a binary 
> variable.
> 
> By minimizing sum of B, I can get the minimum total number of non-zero 
> value. Is there another way to do so?
> 

Reformulation will depend on the rest of the problem,
e.g. if you had a problem like

param a{I,J}, >=0;
var Xmax{j in J}, >= 0, <= ub[j];
var B{J}, binary; 
minimize obj:
  sum{j in J} B[j];
s.t. c1 {i in I} :
  sum{j in J} a[i,j] * Xmax[j] >= 1;
s.t. c2 {j in J} :
  Xmax[j] <= M * B[j];

you could write instead

param a{I,J}, >=0;
var B{J}, binary;
minimize obj:
  sum{j in J} B[j];
s.t. c1 {i in I} :
  sum{j in J} B[j] * ub[j] * a[i,j] >= 1;

Best regards

Xypron

-- 
GMX DSL SOMMER-SPECIAL: Surf & Phone Flat 16.000 für nur 19,99 ¿/mtl.!*
http://portal.gmx.net/de/go/dsl