Skip to main content

Questions tagged [assignment-problem]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
54 views

Linear sum assignment, but with ranked assignments?

Let's say I have 5 tasks that I have to assign to 5 agents, with a cost matrix: ...
Dan's user avatar
  • 1
0 votes
1 answer
77 views

Hungarian Algorithm returns Boolean value for Traveling salesman problem

I am trying to implement Hungarian algorithm right off the shelf on a cost dictionary as part of Traveling salesman problem. The goal is to get path with minimum cost which hopefully covers all cities ...
jayant's user avatar
  • 109
0 votes
0 answers
46 views

Reinforcement learning for a Assignment Problem

I was just wondering if it is technically possible to solve a general assignment problem using reinforcement learning? You could use the inverted objective function as a reward function, right? Have ...
marvelfab12's user avatar
1 vote
1 answer
44 views

Terminology for "One-time" vs. "Continuous Tasks"

I'm working on task scheduling for satellite constellations, and I'm trying to determine if there are any keywords related to a certain distinction in task allocation problem that I'm seeing. In many ...
jgholder's user avatar
  • 111
2 votes
1 answer
97 views

Assignment of colored boxes to groups

I am working on a problem that I think can be solved as an extension to the assignment problem, but am open to hear about other ways to solve. PROBLEM There are a lot of colored boxes. For each color ...
frellwan's user avatar
1 vote
1 answer
66 views

iterative geographic assignment problem

I would like to formulate the following problem: Each state has multiple counties and each county has multiple municipalities. I have treatment cities and possible control cities (more possible ...
user13117's user avatar
0 votes
2 answers
181 views

Algorithms to use for an assignment problem

Here is my problem: There are five sewing lines. When sample orders arrive, we have to assign them to the available line which is more skilled on a particular garment. Each line is given a rank ...
Tharindu Kariyawasam's user avatar
3 votes
2 answers
149 views

Effective methods for solving the assignment and packing problem

There are $m$ items to be allocated into $n$ bins. The profit generated by placing the $i$-th item into the $j$-th bin is $c_{ij}$, and the service level is $s_{ij}$. A allocation scheme is required ...
Ying's user avatar
  • 105
1 vote
4 answers
556 views

Google-OR Tools: Assignment minimizing overlapping members

I'm rusty on constraint optimization and am looking for help in this particular use case. There are individuals who are each member to several teams. This is a fixed many-to-many relationship and is ...
James Kolpack's user avatar
2 votes
1 answer
66 views

Optimizing Storage Allocation and Supply for Manufacturing with Time Constraints

I am currently working on a storage location assignment problem (SLAP), which involves optimizing the allocation of various items with different dimensions to different storage areas. My model ...
Maryam's user avatar
  • 21
0 votes
2 answers
90 views

Formulating assignment problem with people attributes that need to be balanced per assignment attribute in or-tools, CP-sat

I'm trying to do an assignment problem with the following characteristics: I have two sets that need to be matched with each other, set A (Students) and set B (Class combinations). Set A and B have ...
Riezz's user avatar
  • 41
2 votes
3 answers
833 views

Modeling: How to force customers visit their NEAREST facility

Let set $I$ denote the facility location set, $N$ denote the customer set, and $d_{ni}, \forall n\in N, i \in I $ is the distance between customer $n$ and facility $i$. The problem is to locate ...
Runfeng Yu's user avatar
3 votes
1 answer
195 views

Assignment Problem - Students and teachers

I ran across this problem at work and I'm sure that we can optimize it with OR. I have $n(T) = 4$ teachers and $n(S) = 7$ students that should have a weekly individual class. If a student $s$ has a ...
nickh's user avatar
  • 133
0 votes
2 answers
116 views

Assignment problem with multiple precedence constraints

Objective and short problem description The objective is to load as many passenger vehicles as possible on an auto-train. The train consists of multiple wagons with two levels each. The wagons are ...
Christian's user avatar
2 votes
3 answers
117 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 ...
avilog's user avatar
  • 21
1 vote
3 answers
94 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 ...
3Li's user avatar
  • 35
2 votes
3 answers
285 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 ...
BRavos's user avatar
  • 29
1 vote
2 answers
111 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 ...
Jordan C's user avatar
-1 votes
2 answers
153 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 ...
Waldo's user avatar
  • 19
5 votes
2 answers
592 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 ...
YjyJeff's user avatar
  • 153
3 votes
1 answer
131 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$, ...
jbuddy_13's user avatar
  • 551
5 votes
2 answers
277 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: ...
Him's user avatar
  • 153
1 vote
2 answers
110 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 ...
danio1024's user avatar
1 vote
1 answer
204 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 ...
madhatter5's user avatar
3 votes
1 answer
188 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 $ $\...
sgk's user avatar
  • 33
4 votes
1 answer
189 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 ...
Harun Gül's user avatar
2 votes
1 answer
315 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. ...
B Marshall's user avatar
1 vote
0 answers
117 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 ...
PrashanthVajjhala's user avatar
2 votes
0 answers
66 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 ...
Daniel Baquero's user avatar
3 votes
2 answers
69 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: ...
Cyrus Roettern's user avatar
1 vote
1 answer
146 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 ...
Optimization team's user avatar
2 votes
2 answers
237 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 ...
Elis's user avatar
  • 23
2 votes
1 answer
81 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 ...
gameveloster's user avatar
2 votes
1 answer
306 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 ...
Meet Saiya's user avatar
2 votes
0 answers
74 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 ...
mri's user avatar
  • 121
0 votes
1 answer
469 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 ...
falamiw's user avatar
  • 157
2 votes
0 answers
64 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 \...
Yuki's user avatar
  • 29
-1 votes
1 answer
104 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 ...
Harun Gül's user avatar
4 votes
2 answers
298 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$ ...
torayeff's user avatar
1 vote
2 answers
641 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 ...
Linh OR's user avatar
  • 21
1 vote
2 answers
197 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 ...
user5966's user avatar
2 votes
1 answer
98 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 ...
ramgorur's user avatar
  • 129
1 vote
0 answers
47 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 ...
Nyxynyx's user avatar
  • 179
6 votes
1 answer
249 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 ...
Nyxynyx's user avatar
  • 179
3 votes
1 answer
192 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 ...
Athena Wisdom's user avatar
4 votes
1 answer
2k 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 ...
Athena Wisdom's user avatar
2 votes
0 answers
65 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 ...
Luo ArChen's user avatar
1 vote
1 answer
88 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 ...
dkent's user avatar
  • 217
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 ...
Alberto Santini's user avatar
7 votes
3 answers
708 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, ...
G_B's user avatar
  • 1,857