8

I don't think the monotonicity will help much, for the following reason. Start with any arbitrary assignment problem. Add a constant amount $K$ to $c_{i2}$ for all $i$, with $K$ sufficiently large to make $c_{i2} > c_{i1}$ for all $i$. Since someone has to be assigned to sink 2, this effectively adds a constant amount $K$ to the objective function, and so ...


7

Formulating as one big problem requires more memory, some way to recognize that the problem decomposes into disjoint subproblems, and some way to then solve the subproblems independently. At least one commercial solver (SAS) looks for such structure after presolve and suggests using the decomposition algorithm in that case. The decomposition algorithm ...


6

Yes. The ruggedness of a landscape is a measure of how much variability is observed between neighbouring solutions, and it can be computed using the landscape correlation function. Rugged landscapes (with a very low correlation) typically have lots of local minima and are more difficult to traverse than smooth landscapes (correlation close to 1). For a fixed ...


4

Cost matrixes are discussed in the book: "Assignment Problems" by Rainer Burkard, Mauro Dell'Amico, Silvano Martello (on pages 73, and 200, etc.). Yes, some parts would be unconnected (most likely) in such a large problem. Seperation and calculation of the cost matrixes is only the start of the problem. Solving using traditional methods, for so ...


3

Minimizing the sum of all assignments: this is the classical version of the assignment problem. The Hungarian algorithm solves it in polynomial time. Minimizing the maximum of all assignments: this one is known as the linear bottleneck assignment problem. The most obvious way to solve it is to solve a succession a decision problems: is it possible to find ...


Only top voted, non community-wiki answers of a minimum length are eligible