Questions tagged [assignment-problem]
Questions on problems whose solution space are one-to-one mappings between two sets.
66
questions
2
votes
3
answers
105
views
Is there a name for this variation of the generalized assignment problem?
All the input variables are positive float (x > 0). We have $M$ agents with limited amount of time $t_1,\dots,t_M$, $N$ tasks $task_1,\dots,task_N$ associated with duration $d_1,\dots, d_N$. Cost ...
- 21
1
vote
3
answers
61
views
PuLP ensure first and last choice
I have an assignment problem where I have $N$ locations and $M$ dates for each location, and the goal is to choose $K$ location-date pairs that maximize revenue. There are a number of constraints, for ...
- 23
2
votes
2
answers
167
views
How to represent the objective function of the Weapon Target Assignment problem in CVXPY?
I am trying to use CVXPY to analyse a problem and the objective function for this problem involves calculating a product and a sum as per the problem description below (taken from a draft paper I am ...
- 29
1
vote
2
answers
92
views
Alternative Approaches to Assignment Problem
I have a real world use case where I aim to optimize the assignment of trucks to orders of different sizes over a time window by minimizing some cost function (e.g. total distance traveled).
The below ...
- 13
0
votes
2
answers
92
views
Reformulate this constraint optimization problem such that I do not have to divide 2 variables?
I have a constraint optimization problem as follows:
I need to assign $m$ tasks to $n$ days, with $n \geq m$.
Each day can host 0 to $m$ tasks.
Each task either belongs to type $A$ or $B$.
I want to ...
- 21
5
votes
2
answers
431
views
Minimize worker variance assignment problem
I have a problem, which is similar to Assignment Problem, described as follows:
The problem instance has a number of workers and a number of tasks. Any task can only be assigned to a subset of the ...
- 153
3
votes
1
answer
124
views
Expressing $\{0,1\}$ assignment across a matrix in MILP?
I have a MILP (Xpress) constraint, which is doing what I want it to, but I'm struggling to translate it into a LaTeX friendly mathematical expression.
The below code enforces that in the matrix $V$, ...
- 471
5
votes
2
answers
256
views
Adding linear penalties for multiple assignments
I have a multiple assignment problem, with an added cost for "repeat assignments".
For example, consider the cost matrix:
...
- 153
1
vote
2
answers
100
views
How do I approach this optimization problem?
I'm a software dev that's pretty new to OR and want to solve a specific problem I came across at my job. From what I've researched it is a variation of resource-constrained assignment problem, but ...
- 21
1
vote
1
answer
127
views
Assignment problem with constrained number of unique tasks
I have an interesting assignment problem in which I have a cost matrix for workers and tasks, and need to assign each worker to exactly one task to minimize the cost.
However, this is all subject to ...
- 13
3
votes
1
answer
168
views
Assignment problem with mutually exclusive constraints has an integral polyhedron?
I have the following problem
$\min \sum_{i\in I} \sum_{j \in J} c_{ij} x_{ij} $
$s.t. \sum_{j \in J} x_{ij} \leq b_i, \forall i \in I$
$\sum_{j \in S_l} x_{ij} \leq 1, \forall l \in L, i \in I $
$\...
- 33
4
votes
1
answer
176
views
Do my constraints to restrict the splitting of tasks make sense?
I have a problem where there are stations, types and tasks which has to be assigned to each other. Now for me the thing is I want the variable $x$ to be not binary like in assignment problem for ...
- 49
2
votes
1
answer
235
views
Multiple Knapsack with Varying Values
I wish to assign customers to their nearest distribution hubs. These hubs have maximum capacities however, and if these are breached I would like to assign customers to the next most appropriate hub.
...
- 23
1
vote
0
answers
64
views
Assignment problem with continuous constraints
I am trying to solve an assignment problem where all the variables are continuous. I have a set of sources S, and another set of destinations D. Each source and destination have capacity/demand ...
2
votes
0
answers
61
views
Assignment/scheduling how to formulate considering job time and job cost
I have the following problem that I do not know how to formulate.
There are a fixed number of workers $w_i \in W$ for $i \in [1…N]$.
Also, there are a fixed number of jobs that must be assigned to ...
- 169
3
votes
2
answers
62
views
Constrained shift assignment problem using ilogcp solver can´t find an optimal solution
I´ve been trying to solve a contrained assignation problem given a set of constraints based in a real-world problem. I modeled the problem in AMPL as follows:
...
1
vote
1
answer
128
views
How to formulate fleet Assignment Problem?
I do want to formulate a fleet assignment problem. The following table is available
It shows the departure/arrival location and time
I am trying to find the min number of required planes to assign to ...
- 1,120
2
votes
2
answers
162
views
Assign jobs to least people with multiple job constraints
Assume I have an infinite number of staff/supply. I have a table of how much time in hours needs to be spent on certain tasks:
Task
Demand
A
0.75
B
0.8
C
0.65
D
0.7
E
0.6
F
0.65
And the tasks ...
- 23
2
votes
1
answer
73
views
How to do Local search when using Greedy random heuristics for GAP
If I want to try a greedy randomized adaptive search procedure for the generalized assignment problem (assign N tasks to N workers to minimize the total costs), the GRASP method requires 2 parts
...
- 123
2
votes
1
answer
184
views
How to do matrix multiplication in docplex in python?
Here's an applicative problem I'm trying to solve. Imagine there is a road that can be classified in 5 states. Can be something from good to bad etc. There are 4 maintenance actions possible. And the ...
- 57
2
votes
0
answers
59
views
find unique neighbour pairs between two point clouds in R
Given two point clouds I want to find for each point from the first point cloud the nearest neighbour from the second point cloud. Also, each pair of neighbours should be unique. The solution was ...
- 121
0
votes
1
answer
221
views
Can Expected value of perfect information be zero?
I tried to find the Expected Value of Perfect Information (EVPI) and the Value of the Stochastic Solution (VSS) of the following problem.
Consider a farmer who specializes in raising wheat, corn, and ...
- 157
2
votes
0
answers
60
views
Type of combinatorial problem
I'm looking at a problem that looks as follows:
$$
C = \sum_{i =1}^N\sum_{j<i} ( A_{ij} - B_{{P(i)P(j)}} )^2
$$
where $A$ and $B$ are square matrices and $P$ is a permutation matrix mapping all $i \...
- 29
-1
votes
1
answer
83
views
Assignment Problem with continuous decision variable
I have to solve a problem from industry where there are a number of machines which should be assigned to a number of tasks. The difference from the general assignment problem is tough, that the ...
- 49
4
votes
2
answers
263
views
Identifying problem: Assignment + Job Shop Scheduling
I am new to OR. Hence, I want your advice on the problem I am trying to solve:
Given:
$O_1 \rightarrow O_2 \rightarrow O_3 \rightarrow ... \rightarrow O_n$: the sequence of operations to produce $1$ ...
- 99
1
vote
2
answers
422
views
How to solve assignment problem with additional constraints?
The assignment problem is defined as:
Let there be n agents and m tasks. Any agent can be assigned to perform any task, incurring some costs that may vary depending on the agent-task assignment. We ...
- 21
1
vote
2
answers
180
views
How to solve assignment problem with type constraints?
There are $n$ jobs and $m$ machines.
Assigning job $i$ to machine $j$ yields a profit of $c_{ij}$.
Each job has a type $t_i$.
Machine $j$ can take on up to $a_j$ jobs, but the number of job types must ...
- 51
2
votes
1
answer
87
views
Load to ship assignment problem
Problem
We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a ...
- 129
1
vote
0
answers
36
views
Blended or hierarchical objectives if solving speed is more important
When optimizing a two objective task assignment problem, is it generally better to use blended objectives or hierarchical objectives if
the speed to obtaining a near-optimal solution is more ...
- 179
6
votes
1
answer
231
views
Use GA for Assignment Problem?
I have a two-objective assignment problem that appears to converge really slowly to a solution.
Even if we just have 1 objective that minimizes costs, it appears to be very slow for a worker-task ...
- 179
3
votes
1
answer
90
views
LP Objective function for distributing workload
In this example, we have a group of students that each needs to be paired with a teacher. Each student has a different number of questions to ask the teacher, and each student-teacher pairing has a ...
- 243
4
votes
1
answer
1k
views
Difference between solving Assignment Problem using the Hungarian Method vs. LP
When trying to solve for assignments given a cost matrix, what is the difference between
using Scipy's linear_sum_assignment function (which I think uses the ...
- 243
2
votes
0
answers
43
views
Solving minimum bipartite matching with missing edges using Hungarian algorithm
I am interested in a minimum bipartite matching problem, where some edges are missing (i.e., not valid). An intuitive way to solve the problem is to add very large costs for these missing edges and ...
- 61
1
vote
1
answer
65
views
Assignment Problems With More than One Class of Resource
I am working on a dispatch optimization problem in the trucking industry.
I have a first algorithm - a vehicle routing algorithm - that produces a series of tours.
I will need a second algorithm that ...
- 117
11
votes
5
answers
3k
views
A Stack Overflow user's curious problem of maximising unsortedness
User ddofborg posted on Stack Overflow a programming question which hides a combinatorial optimisation problem.
The idea is the following: given a list of URLs with their respective domain names, he ...
- 2,043
7
votes
3
answers
701
views
How to keep solutions stable/persistent in a problem with many equally good solutions?
Suppose we have a worker-assignment problem where we seek to assign Alice, Bob, Chris, ... to jobs A, B, C, ... subject to various constraints and some objective function based on these assignments, ...
- 1,797
2
votes
1
answer
278
views
How to solve a minimum cost flow problem with time constraints
In the following picture, the decision-maker has to make deliveries to node $V=\{1,2,3,4,5,6\}$. He has two options: use cars or bikes. In both cases, he has to make a stop at a relay point where the ...
- 115
8
votes
1
answer
159
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}
$$
...
- 83
2
votes
1
answer
98
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
0
answers
299
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 ...
- 11
3
votes
0
answers
82
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 ...
- 3,207
1
vote
1
answer
73
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 ...
- 137
3
votes
2
answers
499
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 ...
- 51
1
vote
1
answer
96
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
...
- 111
4
votes
1
answer
490
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 ...
- 101
2
votes
2
answers
98
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 (...
- 21
1
vote
0
answers
215
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:
...
- 111
4
votes
1
answer
252
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 ...
- 61
4
votes
1
answer
208
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, ...
- 141
5
votes
1
answer
209
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 \\
&\...
- 123