0
$\begingroup$

I have the following maximization problem that I currently try to solve with Minimize/NMinimize. Unfortunately, this kind of solution method takes really long for large systems of equations and therefore I am looking for an alternative. I saw that I would be able to use LinearProgramming as well. Here are my questions:

1) Would using LinearProgramming speed up the process?

2) If, yes. How would you tranform my Minimize form into LinearProgramming form?

   ClearAll["Global`*"];
pc = 36;
ec = 10;
c = {10., 10., 10., 10., 10., 10., 10., 10., 10., 10.};


L = {{1., 0., 0., 1., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 1., 0., 0., 0., 0., 1., 0., 0., 1., 0., 1., 0., 0., 0., 
    1., 0., 0., 0.}, {0., 1., 1., 0., 0., 1., 0., 0., 0., 0., 1., 0., 
    0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 1., 
    0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 0., 0., 1., 0., 0., 0., 
    0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1.}, {0., 0., 0., 0., 
    0., 0., 0., 1., 0., 0., 1., 1., 0., 0., 1., 0., 1., 0., 0., 0., 
    1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 
    1.}, {0., 0., 0., 1., 0., 0., 1., 0., 1., 1., 0., 0., 1., 1., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 1., 0., 0., 
    0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 
    0., 1., 0., 0., 1., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 1., 0., 0., 1., 0., 1., 0.}, {0., 1., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 1., 0., 0., 
    0., 1., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 1.}, {0., 0., 0., 
    0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 
    0., 0., 1., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 
    0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1., 1., 1., 1., 0., 0., 
    0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 1., 1., 1., 1., 1., 1., 1.}};

H = {{1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0.}, {0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 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., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 0., 0., 
    0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0.}, {0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 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., 0., 0., 0., 0., 0., 
    0.}, {0., 0., 0., 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., 
    0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0.}, {0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 
    0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 
    0., 0., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 1., 1., 0., 0., 0.}, {0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 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., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 
    0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 
    1.}};
fk = {3, 1, 0, 3, 1, 2, 0, 3, 1, 2, 2, 3, 3, 2, 0, 3, 3, 1, 3, 0};



fun[y_, c_] := 
  Piecewise[{{y, 0 <= y/c <= 1/3}, {3 y - (2/3) c, 
     1/3 <= y/c <= 2/3}, {10 y - (16/3) c, 
     2/3 <= y/c <= 9/10}, {70 y - (178/3) c, 
     9/10 <= y/c <= 1}, {70 y - (178/3) c, 
     9/10 <= y/c <= 1}, {500 y - (1468/3) c, 
     1 <= y/c <= 11/10}, {5000 y - (16318/3) c, 
     11/10 <= y/c <= \[Infinity]}}];
(*Define variables*)
y = Table[Unique["y"], {ec}];
x = Table[Unique["x"], {pc}];
variables = Join[y, x];

(*Define constraints*)
constraints1 = L.x == y;
constraints2 = H.x == fk;
constraints3 = x >= 0;
constraints4 = y >= 0;

(*Solve the multi-commodity flow problem*)

solution = 
 NMinimize[{Sum[fun[y[[i]], c[[i]]]/c[[i]], {i, ec}], constraints1, 
   constraints2, constraints3, constraints4}, variables]

It shall be noted that $L$ and $H$ denote matrices with only binary values (1 or 0) and that the objective function is a piecewise-linear approximation of a concave function.

In mathematical notion, the problem thus looks the following, $ \begin{aligned} & \underset{x,y}{\text{minimize}} & &f(y) = \sum_{e \in E} \frac{y_{e}}{c_{e} - y_{e}} \\ & \text{subject to} && \\ &\ & & H\,\, \vec{x} = \vec{f} \ &&&(1)\\ & \ & & L \vec{x} = \vec{y} \ &&&(2)\\ & \ & & \vec{x}\geq 0 \ &&&(3)\\ & \ && 0<y_{e} < c_{e} &&&(4)\\ \end{aligned} $

where, $f(y_{e})$ equals

$ f(y_{e})\approx g(y_{e}) =\frac{\phi_{e}(y_{e},c_{e})}{c_{e}}$

where $ \phi_{e}(y_{e},c_{e})=\begin{cases} y & \text{for } 0\leq \frac{y}{c}\leq\frac{1}{3}\\ 3y-\frac{2}{3}c & \text{for}\frac{1}{3}\leq\frac{y}{c}\leq\frac{2}{3} \\ 10y-\frac{16}{3}c & \text{for}\frac{2}{3}\leq\frac{y}{c}\leq\frac{9}{10} \\ 70y-\frac{178}{3}c & \text{for}\frac{9}{10}\leq\frac{y}{c}\leq 1 \\ 500y-\frac{1468}{3}c & \text{for}1\leq\frac{y}{c}\leq\frac{11}{10} \\ 5000y-\frac{16318}{3}c & \text{for}\frac{11}{10}\leq\frac{y}{c}\leq \infty \\ \end{cases}$

Here, I replace the objective function $f(y)$ with the piecewise-linear approximation of $g(y)$. Since I am now dealing with matrices and a rather dynamic objective function, I am unsure how to apply the LinearProgramming form to this.

Best,

Julian

$\endgroup$
  • 1
    $\begingroup$ Please try to post working code whenever possible $\endgroup$ – Dr. belisarius Nov 16 '14 at 17:23
  • $\begingroup$ I was hoping to avoid this. But you are probably right. I adjusted my code and added all required variables. $\endgroup$ – Julian Nov 17 '14 at 11:55
  • $\begingroup$ I get a solution for this problem using Minimize or NMinimize, however for larger problems it really gets slow even at a server with 8 CPU cores. Therefore I am looking for a faster solution. $\endgroup$ – Julian Nov 17 '14 at 11:57
  • $\begingroup$ Was you able to transform the problem into a LP formulation suitable for LinearProgramming? I think the objective function can pose some problem as is... $\endgroup$ – unlikely Feb 28 '16 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.