Advanced Search

Teep

195 Reputation

5 Badges

16 years, 94 days
Contact Teep

MaplePrimes Activity


These are replies submitted by Teep

The saga continues ... feasibility toler...

Teep 195
December 10 2016
0 0

Hi again.

The procedure you sent worked fine.

However, I need to alter the first constraint to account for a realistic situation. This involved switching the order of i and j.  I get an error message to adjust the feasibility tolerance; when I try to do that, I am prompted to alter the depth limit. I have tried various values .... with no luck (worksheet is uploaded).


 

> 

``

 

 

> 

restart; with(Optimization)
> 

m := 9;

9

  

9

  

3

 (1)

 

> 

dist := Matrix(m, n, [[0, 720, 790, 297, 283, 296, 461, 769, 996], [720, 0, 884, 555, 722, 461, 685, 245, 1099], [790, 884, 0, 976, 614, 667, 371, 645, 219], [297, 555, 976, 0, 531, 359, 602, 715, 1217], [283, 722, 614, 531, 0, 263, 286, 629, 721], [296, 461, 667, 359, 263, 0, 288, 479, 907], [461, 685, 371, 602, 286, 288, 0, 448, 589], [769, 245, 645, 715, 629, 479, 448, 0, 867], [996, 1099, 219, 1217, 721, 907, 589, 867, 0]]):

 

> 

d := Vector([2870000, 572000, 8450000, 350000, 901000, 333000, 306000, 723000, 610000]):

To minimize the objective function, z:

> 

z := add(add(dist[i, j]*d[j]*Y[i, j], j = 1 .. n), i = 1 .. m):

The first constraint is:

> 

for j to n do constraint[j] := add(Y[i, j], i = 1 .. m) = 1 end do;

Y[1, 1]+Y[2, 1]+Y[3, 1]+Y[4, 1]+Y[5, 1]+Y[6, 1]+Y[7, 1]+Y[8, 1]+Y[9, 1] = 1

  

Y[1, 2]+Y[2, 2]+Y[3, 2]+Y[4, 2]+Y[5, 2]+Y[6, 2]+Y[7, 2]+Y[8, 2]+Y[9, 2] = 1

  

Y[1, 3]+Y[2, 3]+Y[3, 3]+Y[4, 3]+Y[5, 3]+Y[6, 3]+Y[7, 3]+Y[8, 3]+Y[9, 3] = 1

  

Y[1, 4]+Y[2, 4]+Y[3, 4]+Y[4, 4]+Y[5, 4]+Y[6, 4]+Y[7, 4]+Y[8, 4]+Y[9, 4] = 1

  

Y[1, 5]+Y[2, 5]+Y[3, 5]+Y[4, 5]+Y[5, 5]+Y[6, 5]+Y[7, 5]+Y[8, 5]+Y[9, 5] = 1

  

Y[1, 6]+Y[2, 6]+Y[3, 6]+Y[4, 6]+Y[5, 6]+Y[6, 6]+Y[7, 6]+Y[8, 6]+Y[9, 6] = 1

  

Y[1, 7]+Y[2, 7]+Y[3, 7]+Y[4, 7]+Y[5, 7]+Y[6, 7]+Y[7, 7]+Y[8, 7]+Y[9, 7] = 1

  

Y[1, 8]+Y[2, 8]+Y[3, 8]+Y[4, 8]+Y[5, 8]+Y[6, 8]+Y[7, 8]+Y[8, 8]+Y[9, 8] = 1

  

Y[1, 9]+Y[2, 9]+Y[3, 9]+Y[4, 9]+Y[5, 9]+Y[6, 9]+Y[7, 9]+Y[8, 9]+Y[9, 9] = 1

 (2)
> 

constraint1 := `union`(`union`(`union`(`union`(`union`(`union`(`union`(`union`({constraint[1]}, {constraint[2]}), {constraint[3]}), {constraint[4]}), {constraint[5]}), {constraint[6]}), {constraint[7]}), {constraint[8]}), {constraint[9]}):

The second constraint is:

> 

constraint2 := {add(X[i], i = 1 .. m) = p}:

The third constraint is:

> 

constraint3 := {seq(seq(Y[i, j] <= X[j], i = 1 .. m), j = 1 .. n)}:

The constraints (4 and 5) require binary outputs; zero or one.  This is automatically accounted for, so removed, since all variables will be assumed binary.

Thus, the consolidated constraints are:

 

> 

constraints := `union`(`union`(constraint1, constraint2), constraint3):

 

The minimized solution is:

> 

z[min] := LPSolve(z, constraints, assume = binary)

Error, (in Optimization:-LPSolve) no feasible integer point found; use feasibilitytolerance option to adjust tolerance

  
> 

``

 

 

 

NULL


 

Download Feasibility_Tolerance.mw

Could you suggest any possible fixes?

Thanks in advance.

@ 

Got it!...

Teep 195
December 09 2016
0 0

Many thanks!

@vv 

Thanks!...

Teep 195
December 09 2016
0 0

I appreciate the guidance - I'm obliged. I did post the worksheet .... thanks again..

@brian bovril 

Thanks! It's much appreciated....

Teep 195
December 09 2016
0 0

@Carl Love 

Please re-send link...

Teep 195
December 09 2016
0 2

Many thanks for the response and effort.

However, the link to the solution is incomplete (I get a blank Word document!).

Would you please re-send the .mws file?

Optimization with binary constraints...

Teep 195
December 08 2016
0 1


 

> 

restart; with(Optimization)

[ImportMPS, Interactive, LPSolve, LSSolve, Maximize, Minimize, NLPSolve, QPSolve]

 (1)
> 

m := 9;

9

  

9

  

3

 (2)

The distance matrix:

> 

dist := matrix(m, n, [[0, 720, 790, 297, 283, 296, 461, 769, 996], [720, 0, 884, 555, 722, 461, 685, 245, 1099], [790, 884, 0, 976, 614, 667, 371, 645, 219], [297, 555, 976, 0, 531, 359, 602, 715, 1217], [283, 722, 614, 531, 0, 263, 286, 629, 721], [296, 461, 667, 359, 263, 0, 288, 479, 907], [461, 685, 371, 602, 286, 288, 0, 448, 589], [769, 245, 645, 715, 629, 479, 448, 0, 867], [996, 1099, 219, 1217, 721, 907, 589, 867, 0]])

array( 1 .. 9, 1 .. 9, [( 3, 7 ) = (371), ( 4, 4 ) = (0), ( 2, 4 ) = (555), ( 3, 1 ) = (790), ( 1, 1 ) = (0), ( 1, 7 ) = (461), ( 9, 2 ) = (1099), ( 9, 8 ) = (867), ( 9, 1 ) = (996), ( 1, 6 ) = (296), ( 5, 8 ) = (629), ( 7, 7 ) = (0), ( 9, 7 ) = (589), ( 4, 5 ) = (531), ( 6, 4 ) = (359), ( 4, 3 ) = (976), ( 8, 5 ) = (629), ( 5, 1 ) = (283), ( 2, 9 ) = (1099), ( 7, 2 ) = (685), ( 7, 3 ) = (371), ( 9, 3 ) = (219), ( 7, 9 ) = (589), ( 1, 2 ) = (720), ( 9, 9 ) = (0), ( 5, 6 ) = (263), ( 6, 3 ) = (667), ( 4, 6 ) = (359), ( 2, 5 ) = (722), ( 5, 3 ) = (614), ( 3, 2 ) = (884), ( 8, 3 ) = (645), ( 8, 9 ) = (867), ( 5, 2 ) = (722), ( 2, 6 ) = (461), ( 4, 2 ) = (555), ( 8, 4 ) = (715), ( 7, 8 ) = (448), ( 9, 4 ) = (1217), ( 1, 5 ) = (283), ( 5, 7 ) = (286), ( 3, 6 ) = (667), ( 3, 4 ) = (976), ( 4, 1 ) = (297), ( 2, 1 ) = (720), ( 2, 7 ) = (685), ( 8, 2 ) = (245), ( 6, 1 ) = (296), ( 8, 8 ) = (0), ( 6, 7 ) = (288), ( 6, 8 ) = (479), ( 4, 7 ) = (602), ( 7, 5 ) = (286), ( 5, 4 ) = (531), ( 1, 9 ) = (996), ( 8, 7 ) = (448), ( 6, 2 ) = (461), ( 7, 4 ) = (602), ( 4, 8 ) = (715), ( 3, 5 ) = (614), ( 1, 4 ) = (297), ( 2, 2 ) = (0), ( 9, 5 ) = (721), ( 6, 9 ) = (907), ( 9, 6 ) = (907), ( 7, 6 ) = (288), ( 5, 9 ) = (721), ( 6, 6 ) = (0), ( 3, 3 ) = (0), ( 3, 9 ) = (219), ( 1, 8 ) = (769), ( 5, 5 ) = (0), ( 2, 3 ) = (884), ( 3, 8 ) = (645), ( 1, 3 ) = (790), ( 8, 1 ) = (769), ( 2, 8 ) = (245), ( 7, 1 ) = (461), ( 4, 9 ) = (1217), ( 8, 6 ) = (479), ( 6, 5 ) = (263) ] )

 (3)

The demand array, d:

> 

d := array([2870000, 572000, 8450000, 350000, 901000, 333000, 306000, 723000, 610000]); sum(d[j], j = 1 .. n)

array( 1 .. 9, [( 1 ) = (2870000), ( 2 ) = (572000), ( 3 ) = (8450000), ( 4 ) = (350000), ( 5 ) = (901000), ( 6 ) = (333000), ( 7 ) = (306000), ( 9 ) = (610000), ( 8 ) = (723000) ] )

  

15115000

 (4)

We seek to minimize the objective function, z:

 

> 

z = Sum(Sum(dist[i, j]*d[j]*Y[i, j], j = 1 .. n), i = 1 .. m);

z = Sum(Sum(dist[i, j]*d[j]*Y[i, j], j = 1 .. 9), i = 1 .. 9)

 (5)
> 

z := sum(sum(dist[i, j]*d[j]*Y[i, j], j = 1 .. n), i = 1 .. m):

 

 

The first constraint is:

``

> 

for i to m do constraint[i] := sum(Y[i, j], j = 1 .. n) = 1 end do:
> 

constraint1 := `union`(`union`(`union`(`union`(`union`(`union`(`union`(`union`({constraint[1]}, {constraint[2]}), {constraint[3]}), {constraint[4]}), {constraint[5]}), {constraint[6]}), {constraint[7]}), {constraint[8]}), {constraint[9]});

{Y[1, 1]+Y[1, 2]+Y[1, 3]+Y[1, 4]+Y[1, 5]+Y[1, 6]+Y[1, 7]+Y[1, 8]+Y[1, 9] = 1, Y[2, 1]+Y[2, 2]+Y[2, 3]+Y[2, 4]+Y[2, 5]+Y[2, 6]+Y[2, 7]+Y[2, 8]+Y[2, 9] = 1, Y[3, 1]+Y[3, 2]+Y[3, 3]+Y[3, 4]+Y[3, 5]+Y[3, 6]+Y[3, 7]+Y[3, 8]+Y[3, 9] = 1, Y[4, 1]+Y[4, 2]+Y[4, 3]+Y[4, 4]+Y[4, 5]+Y[4, 6]+Y[4, 7]+Y[4, 8]+Y[4, 9] = 1, Y[5, 1]+Y[5, 2]+Y[5, 3]+Y[5, 4]+Y[5, 5]+Y[5, 6]+Y[5, 7]+Y[5, 8]+Y[5, 9] = 1, Y[6, 1]+Y[6, 2]+Y[6, 3]+Y[6, 4]+Y[6, 5]+Y[6, 6]+Y[6, 7]+Y[6, 8]+Y[6, 9] = 1, Y[7, 1]+Y[7, 2]+Y[7, 3]+Y[7, 4]+Y[7, 5]+Y[7, 6]+Y[7, 7]+Y[7, 8]+Y[7, 9] = 1, Y[8, 1]+Y[8, 2]+Y[8, 3]+Y[8, 4]+Y[8, 5]+Y[8, 6]+Y[8, 7]+Y[8, 8]+Y[8, 9] = 1, Y[9, 1]+Y[9, 2]+Y[9, 3]+Y[9, 4]+Y[9, 5]+Y[9, 6]+Y[9, 7]+Y[9, 8]+Y[9, 9] = 1}

 (6)

 

The second constraint is:

> 

constraint2 := add(X[i], i = 1 .. m) <= p;

X[1]+X[2]+X[3]+X[4]+X[5]+X[6]+X[7]+X[8]+X[9] <= 3

 (7)

 

The thirs constraint is:

> 

constraint3 := seq(seq(Y[i, j] <= X[j], i = 1 .. m), j = 1 .. n);

Y[1, 1] <= X[1], Y[2, 1] <= X[1], Y[3, 1] <= X[1], Y[4, 1] <= X[1], Y[5, 1] <= X[1], Y[6, 1] <= X[1], Y[7, 1] <= X[1], Y[8, 1] <= X[1], Y[9, 1] <= X[1], Y[1, 2] <= X[2], Y[2, 2] <= X[2], Y[3, 2] <= X[2], Y[4, 2] <= X[2], Y[5, 2] <= X[2], Y[6, 2] <= X[2], Y[7, 2] <= X[2], Y[8, 2] <= X[2], Y[9, 2] <= X[2], Y[1, 3] <= X[3], Y[2, 3] <= X[3], Y[3, 3] <= X[3], Y[4, 3] <= X[3], Y[5, 3] <= X[3], Y[6, 3] <= X[3], Y[7, 3] <= X[3], Y[8, 3] <= X[3], Y[9, 3] <= X[3], Y[1, 4] <= X[4], Y[2, 4] <= X[4], Y[3, 4] <= X[4], Y[4, 4] <= X[4], Y[5, 4] <= X[4], Y[6, 4] <= X[4], Y[7, 4] <= X[4], Y[8, 4] <= X[4], Y[9, 4] <= X[4], Y[1, 5] <= X[5], Y[2, 5] <= X[5], Y[3, 5] <= X[5], Y[4, 5] <= X[5], Y[5, 5] <= X[5], Y[6, 5] <= X[5], Y[7, 5] <= X[5], Y[8, 5] <= X[5], Y[9, 5] <= X[5], Y[1, 6] <= X[6], Y[2, 6] <= X[6], Y[3, 6] <= X[6], Y[4, 6] <= X[6], Y[5, 6] <= X[6], Y[6, 6] <= X[6], Y[7, 6] <= X[6], Y[8, 6] <= X[6], Y[9, 6] <= X[6], Y[1, 7] <= X[7], Y[2, 7] <= X[7], Y[3, 7] <= X[7], Y[4, 7] <= X[7], Y[5, 7] <= X[7], Y[6, 7] <= X[7], Y[7, 7] <= X[7], Y[8, 7] <= X[7], Y[9, 7] <= X[7], Y[1, 8] <= X[8], Y[2, 8] <= X[8], Y[3, 8] <= X[8], Y[4, 8] <= X[8], Y[5, 8] <= X[8], Y[6, 8] <= X[8], Y[7, 8] <= X[8], Y[8, 8] <= X[8], Y[9, 8] <= X[8], Y[1, 9] <= X[9], Y[2, 9] <= X[9], Y[3, 9] <= X[9], Y[4, 9] <= X[9], Y[5, 9] <= X[9], Y[6, 9] <= X[9], Y[7, 9] <= X[9], Y[8, 9] <= X[9], Y[9, 9] <= X[9]

 (8)

 

The following constraints (4 and 5) require binary outputs; zero or one.

 

> 

constraint4 := [seq(seq(Y[i, j] = [0, 1], i = 1 .. m), j = 1 .. n)];

[Y[1, 1] = [0, 1], Y[2, 1] = [0, 1], Y[3, 1] = [0, 1], Y[4, 1] = [0, 1], Y[5, 1] = [0, 1], Y[6, 1] = [0, 1], Y[7, 1] = [0, 1], Y[8, 1] = [0, 1], Y[9, 1] = [0, 1], Y[1, 2] = [0, 1], Y[2, 2] = [0, 1], Y[3, 2] = [0, 1], Y[4, 2] = [0, 1], Y[5, 2] = [0, 1], Y[6, 2] = [0, 1], Y[7, 2] = [0, 1], Y[8, 2] = [0, 1], Y[9, 2] = [0, 1], Y[1, 3] = [0, 1], Y[2, 3] = [0, 1], Y[3, 3] = [0, 1], Y[4, 3] = [0, 1], Y[5, 3] = [0, 1], Y[6, 3] = [0, 1], Y[7, 3] = [0, 1], Y[8, 3] = [0, 1], Y[9, 3] = [0, 1], Y[1, 4] = [0, 1], Y[2, 4] = [0, 1], Y[3, 4] = [0, 1], Y[4, 4] = [0, 1], Y[5, 4] = [0, 1], Y[6, 4] = [0, 1], Y[7, 4] = [0, 1], Y[8, 4] = [0, 1], Y[9, 4] = [0, 1], Y[1, 5] = [0, 1], Y[2, 5] = [0, 1], Y[3, 5] = [0, 1], Y[4, 5] = [0, 1], Y[5, 5] = [0, 1], Y[6, 5] = [0, 1], Y[7, 5] = [0, 1], Y[8, 5] = [0, 1], Y[9, 5] = [0, 1], Y[1, 6] = [0, 1], Y[2, 6] = [0, 1], Y[3, 6] = [0, 1], Y[4, 6] = [0, 1], Y[5, 6] = [0, 1], Y[6, 6] = [0, 1], Y[7, 6] = [0, 1], Y[8, 6] = [0, 1], Y[9, 6] = [0, 1], Y[1, 7] = [0, 1], Y[2, 7] = [0, 1], Y[3, 7] = [0, 1], Y[4, 7] = [0, 1], Y[5, 7] = [0, 1], Y[6, 7] = [0, 1], Y[7, 7] = [0, 1], Y[8, 7] = [0, 1], Y[9, 7] = [0, 1], Y[1, 8] = [0, 1], Y[2, 8] = [0, 1], Y[3, 8] = [0, 1], Y[4, 8] = [0, 1], Y[5, 8] = [0, 1], Y[6, 8] = [0, 1], Y[7, 8] = [0, 1], Y[8, 8] = [0, 1], Y[9, 8] = [0, 1], Y[1, 9] = [0, 1], Y[2, 9] = [0, 1], Y[3, 9] = [0, 1], Y[4, 9] = [0, 1], Y[5, 9] = [0, 1], Y[6, 9] = [0, 1], Y[7, 9] = [0, 1], Y[8, 9] = [0, 1], Y[9, 9] = [0, 1]]

 (9)
> 

constraint5 := [seq(X[i] = [0, 1], i = 1 .. m)];

[X[1] = [0, 1], X[2] = [0, 1], X[3] = [0, 1], X[4] = [0, 1], X[5] = [0, 1], X[6] = [0, 1], X[7] = [0, 1], X[8] = [0, 1], X[9] = [0, 1]]

 (10)

 

 

The consolidated constraints are:

> 

constraints := `union`(`union`(`union`(`union`({constraint1}, {constraint2}), {constraint3}), {constraint4}), {constraint5}):
> 

Sol := minimize(z, constraints, NONNEGATIVE)

Error, (in minimize) unexpected options: {Y[1, 1] <= X[1], Y[1, 2] <= X[2], Y[1, 3] <= X[3], Y[1, 4] <= X[4], Y[1, 5] <= X[5], Y[1, 6] <= X[6], Y[1, 7] <= X[7], Y[1, 8] <= X[8], Y[1, 9] <= X[9], Y[2, 1] <= X[1], Y[2, 2] <= X[2], Y[2, 3] <= X[3], Y[2, 4] <= X[4], Y[2, 5] <= X[5], Y[2, 6] <= X[6], Y[2, 7] <= X[7], Y[2, 8] <= X[8], Y[2, 9] <= X[9], Y[3, 1] <= X[1], Y[3, 2] <= X[2], Y[3, 3] <= X[3], Y[3, 4] <= X[4], Y[3, 5] <= X[5], Y[3, 6] <= X[6], Y[3, 7] <= X[7], Y[3, 8] <= X[8], Y[3, 9] <= X[9], Y[4, 1] <= X[1], Y[4, 2] <= X[2], Y[4, 3] <= X[3], Y[4, 4] <= X[4], Y[4, 5] <= X[5], Y[4, 6] <= X[6], Y[4, 7] <= X[7], Y[4, 8] <= X[8], Y[4, 9] <= X...

  
> 

NULL
> 

NLPSolve(z, constraints, assume = binary)

Error, (in Optimization:-NLPSolve) constraints must be specified as a set or list of equalities and inequalities

  
> 

``


 

Download p-Median_Trial.mw

@brian bovril 

First 7 8 9 Page 9 of 9