# Tag Info

11

Instead of $$\frac{\textrm{Total school income}}{\textrm{Number of areas}} \ge \ 85000$$ you could have a constraint $$\textrm{Total school income} \ge \ 85000 \times \textrm{Number of areas}.$$ In this case, you won't have any problems when the number of areas is zero. It also makes the model linear instead of non-linear, which is usually a good thing. ...

10

You don't get a minimum-weight (perfect) matching by giving preference to smaller weights in the stable marriage problem. Consider $\mathcal{I}=\{a,b\}$ and $\mathcal{J}=\{1,2\}$ and weights $w_{a1}=2$, $w_{a2}=1$, $w_{b1}=100$, and $w_{b2}=2$. In this case matching $\{a2,b1\}$ of value $101$ is the only stable one but the minimum-weight matching is $\{a1,b2\... 9 Here's a formulation that may be rather large but I think is correct. Indices:$i=$job;$j=$worker;$k=$discount factor;$n=$job count for a worker Parameters:$c_{i}=$undiscounted cost of job$i$;$d_{k}=$discount factor for doing$k$jobs ($d_{1}=1.0,d_{2}=0.95,\dots$);$N=$total number of jobs to be assigned Binary variables:$x_{ijk}=1$... 9 I have used a GAP as a subproblem in a previous project where the aim was to solve the single source capacitated facility location problem. I tried several things in order to speed up the computations, and found that the most effective approach was to use exact knapsack separation from the capacity constraints. That is, I basically solved the dual of the "... 8 Maybe the unnecessarily large value for$A$is causing numerical trouble. Try instead$A = \max_{i,j} p_{i,j} = 9$. Probably your$=0$in the declaration of$x$should be$\ge 0$. In fact, you generally need to declare$x$to be binary when you include side constraints. 8 A matching of size$m$in$\mathrm{K}_{n,n}$is uniquely identified by (i) the set of covered vertices in the left partition, for which there are$\binom{n}{m}$choices, (ii) the set of covered vertices in the right position, ditto$\binom{n}{m}$choices, and (iii) a bijection from the covered vertices on the left onto the covered vertices on the right, for ... 8 For each row,$i$(job), assign it to the worker$j$which minimizes$C_{i,j}$. I.e., assign the job to the cheapest worker. For this problem the greedy algorithm is simple and optimal. I'm an American, so you can call it the American algorithm. 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 I find Pulp is extremely easy to use, versatile and has good performance. Check it out here: https://pythonhosted.org/PuLP/solvers.html 7 I'm not a Python user, but I've heard good things about Pyomo, which is an open-source modeling language. In addition to Pyomo, you would need a solver program (from among those they support), but you would not need to worry about any syntax issues related to the solver. 6 You can model this with a binary variable$x_{i,j}$to indicate whether task$i$is assigned to worker$j$, and a binary variable$y_{i,j}$to indicate whether task$i$is the first task assigned to worker$j$in the current batch. The number of switches is then$\sum_{i\ge 2} \sum_j y_{i,j}$because this sum counts the number of times that any worker ... 6 Another possibility is to consider an integer linear extended formulation. Let$\mathcal{A}_b$be the set of valid assignments for base$b$. I.e., an element of$\mathcal{A}_b$determines$\alpha_b$unique positions among the available ones$\{1, \ldots, n\}$, which are the positions taken by items of base$b$in the solution. Denote with$\mathcal{A} = \...

5

The instances you plan to solve are orders of magnitude larger than the ones from the datasets used in the scientific literature on the Generalized Assignment Problem. The largest instances of the literature have $m = 80$ and $n = 1600$. Most algorithms designed for these instances won't be suitable for you. What seems the most relevant in your case are the ...

5

You can formulate this as an instance of the quadratic assignment problem by duplicating the workers and incurring the batching cost only for pairs of duplicate workers. Here's an alternative MIQP formulation that does not double the number of workers. Let binary decision variable $x_{i,j}$ indicate whether job $i$ is assigned to worker $j$. The problem ...

5

I'm not 100% certain, but I think your problem is rather similar to a cutting stock problem. The routes represent "patterns", and the assignment of vehicles to routes is equivalent to choosing how many times each pattern is cut. That last equivalence depends on vehicles being identical (any vehicle can handle any route, and the cost of the route is ...

5

I assume you're applying the matrix version of the algorithm. When you happen to have only one $0$ for A and D the matrix is \begin{align*} \pmatrix{2&9&0&8&8\\2&1&6&0&5\\0&4&3&0&0\\4&8&0&12&6\\3&0&2&1&1} \end{align*} Now continue with Step 3: cover all zeros minimally, and ...

5

A first attempt is to model this problem using a special case of the Quadratic Assignment Problem (QAP), in which we want to assign URLs to positions in the permutation. To make the model smaller, we first note that we don't need to provide the exact position of each URL, because URLs with the same hostname are indistinguishable for the purpose of computing ...

5

So, it turns out that this problem admits a linear-time exact algorithm! The intuition is to add to the extremes (first and last position) two items with the same base $b^*$, which must be the base with the most items ($b^* = \text{argmax} \{\alpha_b\}$). Then one can reduce by 2 the number of items in this base ($\alpha_{b^*} \gets \alpha_{b^*} - 2$), cut ...

4

A more recent alternative is Python-MIP. It has built-in support of COIN-OR CBC. In addition, right now it supports one commercial solver, namely Gurobi. According to its website, it provides access to advanced solver features like cut generation, lazy constraints, MIP starts and solution pools. Since Python-MIP is mentioned on the COIN-OR projects webpage, ...

4

This reminds me a little of the maximum expected covering location model (MEXCLP) by Daskin (1983). The objective function depends nonlinearly on the number of facilities that cover each customer. Binary decision variables are used to count these assignments, similar to the $y_{jn}$ variables in @prubin's answer, and (again like in @prubin's answer), the ...

4

From the comments I found that your problem can be described by a setup time $s_j$ for process $j$ a travel time $c_{ij}$ for worker $i$ to process $j$ Then the waiting time that we get when assigning worker $i$ to process $j$ is given by $w_{ij}:=|s_j-c_{ij}|$. Using $w_{ij}$ as your new weights of the assignments you can use any classic assignement ...

4

I didn't find a way to express the transition constraints so i give a description what this does and mention what it lacks. using JuMP using Gurobi #needs Gurobi license but any other MILP solver callable from JuMP should work too## Heading ## using UnicodePlots are dependencies. I used UnicodePlots for debugging. It is neat. In Julia dependencies can be ...

4

If I understand correctly, you can enforce the time constraint implicitly by omitting arcs. For each customer, there is a unique path by car and a unique path by bike. If the bike is too slow to meet a customer’s deadline, omit the arc from the bike relay point to that customer. After performing this preprocessing for all customers, solve a pure minimum-...

4

A genetic algorithm with a permutation type chromosome works well on this problem. I have an R notebook demonstrating the approach that can be downloaded here. Since a GA is a metaheuristic, there is no guarantee of optimality, but it seems to perform pretty well (and quickly) on test problems.

3

If the bipartite graph is $K_{n,n}$, then all $n$ vertices of the left hand size have exactly $n$ possible matches (each node of the right layer is a candidate). So the total number of matchings is $n^n$ indeed. Maybe you can try and detect if there are identical matchings among the $3174$ found by CPLEX ?

3

I think the problem is NP-hard since: it will reduce to the 0-1 Knapsack problem with an equality constraint; and, changing $\leq$ to $=$ in the 0-1 Knapsack constraint does not change its complexity (see explanation below). So, your problem is NP-hard as 0-1 Knapsack is. P.S. To see why (2) is correct, suppose all weights and values are equal. Then the ...

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 ...

3

I tried to find the below-cited paper to read and answer your question but unfortunately, I couldn't find that. Anyway, in this paper, the authors investigated VRPPDTW (Vehicle Routing Problem with Pick up and Delivery with Time Windows) and proposed an exact algorithm (there are also some heuristic and metaheuristic approaches to solve this type of VRPs) to ...

3

AFAIK, one of an efficient way to solve Generalized Assignment Problem (GAP), is using Branch and Price technique. I will hope, this or this link be useful.

3

You could try using the greedy heuristic to get an initial solution and then try out one of the many neighborhood-search type metaheuristics. I mentioned sorting on $p_{ij}$ in a comment, but it might (or might not) be better to sort on $p_{ij}/w_{ij}$ (or, time permitting, try both and pick the better solution). For improving on the starting solution, GRASP ...

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