Skip to main content

Questions tagged [assignment-problem]

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

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
181 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 ...
Discrete lizard's user avatar
3 votes
0 answers
97 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 ...
Joris Kinable'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
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
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
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
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
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
1 vote
0 answers
397 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 ...
Dr. Turkuaz's user avatar
1 vote
0 answers
271 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: ...
lyinch's user avatar
  • 111
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
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
-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