Ozzah
Reputation
Next privilege 250 Rep.
 Mar20 awarded Curious Jul15 comment Differential equation True/ False Since there are no given bounds on C, (C could be +ve, -ve, or zero), the answer (true or false) does not depend on what the limits of integration are for F(x) and G(x). May21 awarded Disciplined May11 accepted Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? May9 comment Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? By the way, I though you might be interested to know I implemented this model in CPLEX as a fully ILP with some additional constraints. The objective is the sum of each individual machine costs, and the machine costs are calculated in the same way as in the original objective, only disaggregated. Then I said $Z_i \geq Z_{i + 1}$, meaning the machine costs must be descending. This was an attempt to break symmetry. I found that the performance was quite a lot poorer than without the symmetry breaking constraints. May9 comment Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? Ok, I understand. The solution for each individual machine will unavoidably be identical and the solution will not be primal feasible (obviously), however the lower bound should be tighter than the lower bound from the standard linear relaxation. In other words, I can't use this method to solve the problem, I would need to have this method embedded inside B&B or some other procedure. May8 comment Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? I notice your formulation and Lagrangean relaxation has the same problem as my formulation. If I construct a separate subproblem for each machine, they are all necessarily identical. If I solve the subproblem for machine $i$, I will get the exact same solution for machine $i+1$. Should I be solving each machine separately or all at once? I assume solving them all at once in one model will still not overcome the problem where each individual machine's solution will be identical to the others. May7 awarded Commentator May7 comment Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? Also, thank you very much for the symmetry breaking reference. I was aware of the problems regarding solution symmetry but was unaware how to overcome them for this particular problem. I had avoided at least $n-1$ identical solutions by enforcing job $1$ to be on machine $1$. Since job-machine pairings are irrelevant, this doesn't alter the final solution at all. I could enforce more job-machine pairs to further reduce symmetry, but that would no longer guarantee a truly optimal solution as I would be making assumptions. May7 comment Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? By the way, my original formulation was totally linear and not quadratic. I had the same sort of $z_{ijk}$ variable as you suggest. I found that the performance of this approach was significantly worse than the quadratic formulation. For my problem size (n = 7, m = 65, a = 7, b = 10), it would take almost 24 hours to solve the linear version using B&B, whereas with the quadratic formulation it only took about 3 hours. May6 answered LP relaxation for ILP\IP (integer linear programming) May6 revised Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? added 12 characters in body May5 revised Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? added 68 characters in body May5 asked Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems? May2 answered How is the upper bound of a minimisation IP determined during branch-and-bound? Jul31 asked Can one zero-pad data prior to Fourier transformation, then reverse the change afterwards? Jul21 comment Does a linear expression exist for these ILP variables? Ok, well using "standard" operators that can be used in ILP, that's $X_{i,j,k}=Y_{i,j} \times Z_{i,k}$. This is obvious, however it's certainly non-linear. Jul19 comment Does a linear expression exist for these ILP variables? Sorry, I guess I forgot to mention that. One subject is run at most once, and a subject is taught by exactly one lecturer if we choose to run it. In other words, you can be sure that Y and Z can be mapped to X, however I just need to know if it can be done explicitly, in a single, linear expression. Jul19 comment Does a linear expression exist for these ILP variables? If Y_i,j = 1 and Z_i,k = 1, then X_i,j,k must necessarily also be 1, by definition. That's the whole point. Jul19 comment Does a linear expression exist for these ILP variables? I'm sorry, I don't understand your second possibility at all?