# Tag Info

## Hot answers tagged assignment-problem

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 ... 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 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. 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$0for 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 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 variablex_{i,j}$indicate whether job$i$is assigned to worker$j$. The problem ... 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 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 ... 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 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 ... 2 In your greedy algorithms you are assigning$n-1$people to jobs by for _ in range(n - 1). Thus you are assigning one job too little - even though this choice is trivial it is missing in your objective. When fixing it to$n$this should solve your problem. Just because I couldn't resist not mentioning it. There are extremely good polynomial time exact ... 2 int nbPilots = 50; int nbLocations = 7; int nbDays = 30; range pilots = 1..nbPilots; range days = 1..nbDays; range locations = 1..nbLocations; //decision variable/ dvar boolean assign [pilots][days][locations] ; dvar boolean rest [pilots][days][locations]; //objective/ minimize sum(i in pilots, j in days, l in locations)assign[i][j][l]; //... 2 As suggested above, PULP is one of the open source solver. Apart from this, the best MILP solver available in open source is preferably offered in SCIP optimization suite. I think Google OR tools are built using SCIP only. Moreover, you can refer to COIN-OR where researchers from ORMS society have maintained their projects. 2 When you have two objective functions, and your client can't articulate exactly how the two are to be weighed against one another, sometimes the easiest solution is to avoid making that decision. Instead of trying to figure out the client's priorities and find the single best solution, you can present them with a small list of options guaranteed to contain ... 1 A Boolean linear programming formulation is given for the problem. Let suppose to have$S=[ 1,2, \cdots, n ] $students and$T=[ 1,2, \cdots, m ]$training classes. Let introduce$m \cdot n $variables designated as$x_{i,j}$where$i=1,2, \cdots, n$and$j=1, 2, \cdots, m\$. For every student is know in advance his ready time that is the day in which student ...

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