Questions tagged [assignment-problem]
Questions on problems whose solution space are one-to-one mappings between two sets.
29
questions
8
votes
1answer
116 views
A variant of weighted perfect bipartite matching
I am currently working on weighted perfect bipartite matching, i.e., assignment problem.
Formally speaking, it could be formulated as follows:
$$
min \sum\limits_{i=1}^{N}\sum_{j=1}^{N}c_{ij}x_{ij}
$$
...
2
votes
1answer
66 views
Optimization Problem: Recommending Service Providers to Clients
I am new to optimization, not sure if the problem described below is trivial. Any guidance on solution or nudge in the right direction would be very helpful.
Problem:
There are two groups – clients ...
1
vote
0answers
82 views
Adding sequence constraints to the assignment problem- Python
This is an online assignment problem and yet can be considered as an assignment problem with a sequence. Assume that workers are coming into the system sequentially and I want to assign a task to them ...
3
votes
0answers
59 views
Resource scheduling problem with synchronization constraints: Weak LP relaxation
I have a resource assignment/scheduling problem which involves assigning jobs to $m$ workers. There are 2 sets of different jobs, $J^1$ and $J^2$, and a set of periods $T$.
Let $d_{jt}$ be the number ...
1
vote
1answer
56 views
Print Intermediate Solutions of Scheduling Problem and tackling FLAGS in jupyter notebook
I tried this code and it goes on and I'm clueless when it'll end so I manually interrupt it.
Is there any way we can see intermediate solutions that are feasible solutions and can we limit time or ...
3
votes
2answers
149 views
How to solve large scale generalized assignment problem
I am looking for a way to solve a large scale Generalized assignment problem(To be precise, it is a relaxation of the Generalized assignment problem, because the second constraint has $\le$ instead of ...
1
vote
1answer
56 views
Employee allocation based on ranking: Mathematical Model
Suppose I have three employees and I have to assign three employees based on their ranks. If an employee has rank 1 that means he is best. Say, I have the following table
...
4
votes
1answer
333 views
Assignment and scheduling problem with resource constraints
I have 10 tasks with 6 workers. Each worker can only serve one task at a time and must complete the task before moving on to the next task. Each worker has a maximum work output value and each task ...
2
votes
2answers
87 views
Relationship aware task scheduling heuristics
I have a task scheduling/assignment on machines problem (like a classic bin packing problem) with a twist in which the placement/assignment of one task affects the placement/assignment of other tasks (...
1
vote
0answers
70 views
LP instead of IP formulation of assignment problem
In the example files of GLPK, the assignment problem is written as a linear program. I don't understand why this isn't an integer programming problem. The problem formulation:
...
4
votes
1answer
194 views
Assignment problem with batching costs
I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer ...
4
votes
1answer
102 views
Assignment Problem With Weighted Bipartite Graph
I have the following problem:
Given $n$ workers and $n$ tasks I have to assign a worker to each task where each worker has a time to get to the task, and each task has a preparation time.
for example, ...
5
votes
1answer
95 views
NP-hardness of a special case of multiple choice knapsack problem
Let us consider the following problem:
\begin{align}
\max &\quad\sum_{i=1}^n\sum_{j=1}^m v_{i,j}\cdot x_{i,j} \\
\text{s.t.}&\quad \sum_{i=1}^n x_{i,j} =1 &\forall j =1,\dots,m \\
&\...
2
votes
1answer
115 views
How to determine least time required to complete all tasks?
I am trying to figure out how can I assign tasks to workers in a way that maximum time required to complete all tasks is minimum.
Suppose I have following matrix
...
4
votes
1answer
66 views
Greedy algorithms for assignment problems --- prediction doesn't match simulation
I'm considering the following basic assignment problem: a group of $n$ people is to be assigned, in one-to-one fashion, a set of $n$ jobs. Write $C_{ij}$ for the cost incurred when person $i$ gets ...
3
votes
1answer
343 views
Simplex (GLPK) doesn't find a feasible solution on this simple assignment problem, but there is an obvious one
Problem
Assign 11 projects to 11 students, based on their preference.
For this example, each students chooses only one project, for simplicity shake (as shown below). Student 1 one chooses project 1, ...
5
votes
2answers
210 views
Counting the number of matchings in a complete bipartite graph
I am trying to count the number of matchings in a complete bipartite graph (perfect as well as imperfect). It's relatively easy for me to convince myself that there is $n!$ perfect matchings in the ...
1
vote
1answer
406 views
How to allow multiple assignments for jobs in Hungarian Algorithm?
In the Hungarian Algorithm, the assignment for a bipartite graph considers the restriction of assigning a single job to a single person for example. Can this restriction be relaxed? I would like to ...
1
vote
1answer
79 views
9
votes
4answers
1k views
Open Source MILP software for Python with user-friendly API to define the optimization problem
Following the accepted answer to
Assignment problem where assignments must be done sequentially
I would like to write a Python script which can solve the problem defined there. It's a Mixed Integer ...
6
votes
2answers
423 views
Assignment problem where assignments must be done sequentially
I have a weird planning problem. I think it falls under the assignment category, but I'm not sure because I'm not familiar with assignment problems, and also because there is a "temporal" angle to it, ...
11
votes
2answers
239 views
Generalized Assignment Problem as the sub-problem
I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable?
Moreover, is there any usage of this ...
11
votes
2answers
196 views
Difficulties with finding equivalent problem on literature
I'm working with a sort of pickup delivery problem right now.
We need to assign vehicles to routes and requests to those vehicles. Each request has its due date, client and may be delivered in one of ...
7
votes
1answer
1k views
Excel Solver linear programming - Is it possible to use average of values as a constraint without #DIV/0! errors or sacrificing linearity?
I'm trying to create an assignment optimization model where the areas are assigned to either the south or north school districts so that the total distance is minimized. Each school must have at least ...
11
votes
1answer
281 views
Modeling an assignment/scheduling problem to minimize total wait
I have an assignment type problem in which there is a set of students, $S$, and a set of training classes $T$. Each training has a fixed start and end day and can accommodate at most 1 student. In ...
11
votes
2answers
226 views
Assignment Problem with Decreasing Costs
Problem: I have $i$ jobs that I can assign to $j$ workers. Each job has a cost. Each worker can perform up to an arbitrary max number of jobs. However, there is a cost efficiency for each job that is ...
9
votes
0answers
102 views
Modelling resource dependency in the assignment problem
The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from ...
8
votes
1answer
346 views
Assignment problem using Hungarian method
There are five jobs to be assigned to five machines and associated cost matrix is as follows
$$
\begin{matrix}
\text{Machine} & 1 & 2 & 3 & 4 & 5 \\
\text{Job A} & [11, &...
10
votes
1answer
123 views
Relationship between the Assignment Problem and the Stable Marriage Problem
Suppose I'm solving a minimum-weight matching problem in a bipartite graph with sets $\mathcal{I}$ and $\mathcal{J}$, where $w_{ij}$ denotes the weight of matching item $i$ to $j$. I can model the ...
