algorithms – Solving quadratic assignment problem with two metrics using MIP solver

The problem is the following following:

N = {1,...,m} - servers;
Q = {q{1},...,q{m}} - the required amount of resources for tasks, where qi is the required amount of resources for task i;
T = {1, ..., k} - tasks;
V = {v{1}, ..., v{k}} - the amount of resources on servers, where vi is the amount of resources on server i;
DA - the matrix with the amount of data transferred between tasks. DA{i,j} is the amount of data transferred between task i and task j;
NC - the matrix with the network speeds between servers. NC{i,j} is the network speed between server i and server j;
IC - the matrix with a penalty for assigning two tasks on the same server. IC{i,j} is the penalty for assigning task i and task j on the same server;
x{i,j} = 0 if task i is assigned on server j and x{i, j} = 1 if task i is not assigned on server j

I want to minimize the total communication time and minimize the total penalty in two steps. The first step is to minimize the total penalty and the second step is to minimize the total communication time with the penalty constraint.

Total communication time:
enter image description here

Total penalty:
enter image description here

each task is assigned to exactly on server:
enter image description here

the total required amount of resources for tasks on servers does not exceed the available amount of resources on the servers:
enter image description here

enter image description here

Hence the optimization problem is:
enter image description here

To make the objective function linear, I add constraints z{t1,t2,n1,n2} >= x{t1,n1}+x{t2,n2}-1, z{t1,t2,n1,n2} <= x{t1,n1}, z{t1,t2,n1,n2} <= x{t2,n2}, 0 <= z{t1,t2,n1,n2} <= 1

First step:
enter image description here

Let min_penalty be the result of the first step, then the second step:
enter image description here

Is everything correct?

P.S. Sorry for the grammar mistakes and formatting.

equation solving – Why isn’t this expression returning true to being positive when it is clearly positive?


Expre10 = (B^2/C + 2 B + B^2/D + (B C)/D + (B D)/C) + 
   1 (C + D) - (A (Beta) (Sigma))/(B C D) (C + D);
Assuming({A > 0, B > 0, C > 0, 
  D > 0, (Beta) > 0, (Sigma) > 0, (A (Beta) (Sigma))/(B C D) <=  
   1}, Simplify(Expre10 > 0))

Returns the inequality:

B (B + C) (B + D) > A (Beta) (Sigma)

But we clearly see if (A (Beta) (Sigma))/(B C D) <= 1 holds then our inequality will always be true, so why am I getting the wrong output?

probability – Why solving this integral so difficult?

Let $X_i$ be chosen uniformly and independently from $(0,1)$ for $i = 0, 1, 2, 3, cdots$. For each such $i$. define

$$Y_{i}=X_{0} cdot X_{1}^{-1} cdot X_{2} cdot X_{3}^{-1} cdot ldots cdot X_{i}^{(-1)^{i}}$$

Find the probability that there exists $N$ with $Y_N < 1/2$ and $Y_i < 1$ for all $i < N$.

Partial Solution:

Let $E$ be the event that there is some $Ngeq 0$ such that $Y_N<1/2$ and $Y_i<1$ for all $i<N$. Define a function $f$ by $f(t)=P(E|X_0=t)$. Since $(X_1,X_2)$ is uniform on $(0,1)times (0,1)$ we have from the total law of probability that $$f(t)=int_0^1 int_0^1P(E|X_0=t,X_1=x,X_2=y)mathrm{d}ymathrm{d}x$$ Clearly $f(t)=1$ whenever $t<1/2$. Let’s now assume $t geq 1/2$. Using the fact that $$P(E|X_0=t,X_1=x,X_2=y)=P(E|Y_0=t,Y_1=t/x,Y_2=ty/x)$$ we get $$
Pleft(E mid X_{0}=t, X_{1}=x, X_{2}=yright)= begin{cases}0 & x leq t \ 1 & x>t, y<frac{x}{2 t} \ f(t y / x) & x>t, y geq frac{x}{2 t}end{cases}
Plugging this into the double integral and performing some routine calculus yields the following expression that’s only valid $t geq 1/2$: $$f(t)=frac{1-t^2}{4t}+frac{1-t^2}{2t}int_{1/2}^tf(x)mathrm{d}x+frac{t}{2}int_t^1Big(frac{1}{x^2}-1Big)f(x)mathrm{d}x$$ If you can find $f(t)$ from this expression then $P(E)=int_0^1f(t)mathrm{d}t$ and we’re done.

I am stuck solving an integral equation. Any helps?

Solving recurrence relation $T(n) = 5T(frac{n}{3}) + 2n$

This is not a difficult problem, but I would like please to discuss with you how I solved it:

Solving recurrence relation $T(n) = 5T(frac{n}{3}) + 2n$, $T(1)=2$. What is the value of $T(9)$? This can be done directly by applying $T(9)$ to get 98. However, I did it recursively as follows:

T(n) = 5left(5T(frac{n-1}{3^2}) + 2(n-1)right) + 2n tag{1} \
T(n) = 5left(5left(5T(frac{n-2}{3^3}) + 2(n-2)right) + 2(n-1)right) + 2n\
= 5^3 T(frac{n-2}{3^3}) + 5^2times2(n-2) + 5times2(n-1) + 2n tag{2} \
T(n) = 5^n times Tleft(frac{n-(n-1)}{3^n}right) + 5^{n-1}times2(n-(n-1)) + cdots 5times2(n-1) + 2n tag{3} \

Question: what is the value of $T(n)$ above please as we have $n$, so we can not infinite apply geometric series I guess please?

equation solving – Superfluous un-simplifiable condition returned by Reduce

No real “problem” here, just wondering why this is happening and how one might force Mathematica to simplify this. Consider:

Reduce((-1)^n == 1, n (Element) Reals)

(* Out: (C(1) (Element) Integers && n == 2 C(1)) || n == 0 *)

Note the weird “... || n == 0” even though that’s a special case of the left disjunct, with C(1) -> 0. Applying Simplify and FullSimplify don’t get rid of the superfluous n == 0 condition. (Including the assumption 0 (Element) Integers doesn’t help either; it immediately evaluates to True.)

Another strange thing is that

Reduce((-1)^n == 1, n (Element) Integers)

doesn’t include the superfluous condition! It just returns (C(1) (Element) Integers && n == 2 C(1)).

What’s causing this, and is there a general “lack of ability to unify special cases” in Simplify and the like that it’s worth watching out for? And why does using Integers instead of Reals change the behavior?

equation solving – Prove an inequality over the reals, given a constraint

Given $$a + b + c = 3$$


$$frac{a}{b^2 + 1} + frac{b}{c^2 + 1} + frac{c}{a^2 + 1} geq frac{3}{2}$$

One can prove the above using a great deal of “human” insight and equation manipulation, as shown here.

I would like to prove this with as much automatic symbol manipulation as possible. I’ve tried obvious techniques using Solve, RootIntervals, and such, including the naive directly testing logically:

Assuming(a + b + c == 3,
 a/(b^2 + 1) + b/(c^2 + 1) + c/(a^2 + 1) <= 3/2)

all without success.

I have a sense there must be some way of automatically finding a solution domain for the second equation (given the constraint of the first equation), but have not been able to find it.

equation solving – Using NSolve to get a solution for Bessel-related functions

I want to get a solution of a equation using NSolve.


So I plugged this equation to NSolve:

NSolve(BesselI(1,x)/(x*BesselI(0,x))==0.2, x)

But when I use this, the Mathematica gives the same expression. I know that this equation has such a solution from plot:

enter image description here

Could you let me know how to solve this problem?

Any helps will be appreciated. Thank you!