162 reputation
9
bio website
location Sydney, Australia
age 30
visits member for 3 years, 9 months
seen Nov 20 at 1:08

Jul
15
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).
May
21
awarded  Disciplined
May
11
accepted Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?
May
9
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.
May
9
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.
May
8
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.
May
7
awarded  Commentator
May
7
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.
May
7
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.
May
6
answered LP relaxation for ILP\IP (integer linear programming)
May
6
revised Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?
added 12 characters in body
May
5
revised Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?
added 68 characters in body
May
5
asked Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?
May
2
answered How is the upper bound of a minimisation IP determined during branch-and-bound?
Jul
31
asked Can one zero-pad data prior to Fourier transformation, then reverse the change afterwards?
Jul
21
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.
Jul
19
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.
Jul
19
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.
Jul
19
comment Does a linear expression exist for these ILP variables?
I'm sorry, I don't understand your second possibility at all?
Jul
19
asked Does a linear expression exist for these ILP variables?