Questions tagged [assignment-problem]

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

Filter by
Sorted by
Tagged with
5
votes
2answers
169 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
177 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
72 views

ILOG Cplex out of scope

...
9
votes
4answers
811 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
302 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, ...
5
votes
0answers
29 views

Restricted assignment problem with variable required tasks: feasibility in docplex.cp

I am trying to solve a kind of restricted assignment problem in which the tasks required are dependent of the user input. Let me suppose that the user can enter a set of requirements. According to ...
11
votes
2answers
215 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
166 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
709 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
241 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
193 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
86 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 ...
7
votes
1answer
227 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
110 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 ...