Questions tagged [assignment-problem]

Questions on problems whose solution space are one-to-one mappings between two sets.

Filter by
Sorted by
Tagged with
3 votes
0 answers
69 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$ ...
user avatar
  • 139
1 vote
2 answers
98 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 ...
user avatar
  • 21
1 vote
2 answers
136 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 ...
user avatar
  • 51
2 votes
1 answer
55 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 ...
user avatar
  • 129
1 vote
0 answers
32 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 ...
user avatar
  • 179
6 votes
1 answer
189 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 ...
user avatar
  • 179
3 votes
1 answer
60 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 ...
user avatar
4 votes
1 answer
312 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 ...
user avatar
2 votes
0 answers
31 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 ...
user avatar
1 vote
1 answer
57 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 ...
user avatar
  • 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 ...
user avatar
2 votes
1 answer
156 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 ...
user avatar
  • 51
8 votes
1 answer
129 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} $$ ...
user avatar
2 votes
1 answer
69 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 ...
user avatar
1 vote
0 answers
174 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 ...
user avatar
3 votes
0 answers
68 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 ...
user avatar
1 vote
1 answer
63 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 ...
user avatar
3 votes
2 answers
238 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 ...
user avatar
  • 51
1 vote
1 answer
66 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 ...
user avatar
  • 111
4 votes
1 answer
373 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 ...
user avatar
  • 101
2 votes
2 answers
93 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 (...
user avatar
1 vote
0 answers
123 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: ...
user avatar
  • 111
4 votes
1 answer
211 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 ...
user avatar
4 votes
1 answer
141 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, ...
user avatar
  • 141
5 votes
1 answer
123 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 \\ &\...
user avatar
  • 123
2 votes
1 answer
207 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 ...
user avatar
  • 205
4 votes
1 answer
81 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 ...
user avatar
  • 143
3 votes
1 answer
489 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, ...
user avatar
5 votes
2 answers
266 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 ...
user avatar
  • 1,011
1 vote
1 answer
538 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 ...
user avatar
  • 871
1 vote
1 answer
81 views

ILOG Cplex out of scope

...
user avatar
  • 11
9 votes
4 answers
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 ...
user avatar
  • 255
6 votes
2 answers
519 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, ...
user avatar
  • 255
11 votes
2 answers
261 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 ...
user avatar
11 votes
2 answers
204 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 ...
user avatar
  • 513
7 votes
1 answer
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 ...
user avatar
11 votes
1 answer
325 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 ...
user avatar
  • 111
11 votes
2 answers
235 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 ...
user avatar
  • 309
9 votes
0 answers
124 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 ...
user avatar
8 votes
1 answer
422 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, &...
user avatar
  • 83
10 votes
1 answer
159 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 ...
user avatar
  • 101