11
votes
Accepted
Excel Solver linear programming - Is it possible to use average of values as a constraint without #DIV/0! errors or sacrificing linearity?
Instead of
$$\frac{\textrm{Total school income}}{\textrm{Number of areas}} \ge \$ 85000$$
you could have a constraint
$$\textrm{Total school income} \ge \$ 85000 \times \textrm{Number of areas}.$$
In ...
- 6,063
10
votes
Relationship between the Assignment Problem and the Stable Marriage Problem
You don't get a minimum-weight (perfect) matching by giving preference to smaller weights in the stable marriage problem. Consider $\mathcal{I}=\{a,b\}$ and $\mathcal{J}=\{1,2\}$ and weights $w_{a1}=2$...
- 2,705
9
votes
Assignment Problem with Decreasing Costs
Here's a formulation that may be rather large but I think is correct.
Indices:
$i=$ job;
$j=$ worker;
$k=$ discount factor;
$n=$ job count for a worker
Parameters:
$c_{i}=$ undiscounted cost of ...
- 37.8k
9
votes
Generalized Assignment Problem as the sub-problem
I have used a GAP as a subproblem in a previous project where the aim was to solve the single source capacitated facility location problem. I tried several things in order to speed up the computations,...
- 6,352
8
votes
Accepted
Simplex (GLPK) doesn't find a feasible solution on this simple assignment problem, but there is an obvious one
Maybe the unnecessarily large value for $A$ is causing numerical trouble. Try instead $A = \max_{i,j} p_{i,j} = 9$.
Probably your $=0$ in the declaration of $x$ should be $\ge 0$. In fact, you ...
- 30.4k
8
votes
Counting the number of matchings in a complete bipartite graph
A matching of size $m$ in $\mathrm{K}_{n,n}$ is uniquely identified by (i) the set of covered vertices in the left partition, for which there are $\binom{n}{m}$ choices, (ii) the set of covered ...
- 201
8
votes
Accepted
How to allow multiple assignments for jobs in Hungarian Algorithm?
For each row, $i$ (job), assign it to the worker $j$ which minimizes $C_{i,j}$. I.e., assign the job to the cheapest worker. For this problem the greedy algorithm is simple and optimal.
I'm an ...
- 13.1k
8
votes
Accepted
A variant of weighted perfect bipartite matching
I don't think the monotonicity will help much, for the following reason. Start with any arbitrary assignment problem. Add a constant amount $K$ to $c_{i2}$ for all $i$, with $K$ sufficiently large to ...
- 37.8k
7
votes
Accepted
Open Source MILP software for Python with user-friendly API to define the optimization problem
I find Pulp is extremely easy to use, versatile and has good performance. Check it out here: https://pythonhosted.org/PuLP/solvers.html
- 1,333
7
votes
Open Source MILP software for Python with user-friendly API to define the optimization problem
I'm not a Python user, but I've heard good things about Pyomo, which is an open-source modeling language. In addition to Pyomo, you would need a solver program (from among those they support), but you ...
- 37.8k
7
votes
How to keep solutions stable/persistent in a problem with many equally good solutions?
IMHO, the question and posted answer confuse some different issues:
Reproducibility. This is about finding the same solution when running the algorithm again with the same input, i.e. providing ...
- 2,585
7
votes
Difference between solving Assignment Problem using the Hungarian Method vs. LP
The main differences probably are that there is a somewhat large overhead you have to pay when solving the AP as a linear program: You have to build an LP model and ship it to a solver. In addition, ...
- 6,352
6
votes
Accepted
Assignment problem where assignments must be done sequentially
You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to ...
- 30.4k
6
votes
A Stack Overflow user's curious problem of maximising unsortedness
Another possibility is to consider an integer linear extended formulation.
Let $\mathcal{A}_b$ be the set of valid assignments for base $b$. I.e., an element of $\mathcal{A}_b$ determines $\alpha_b$ ...
5
votes
Accepted
How to solve large scale generalized assignment problem
The instances you plan to solve are orders of magnitude larger than the ones from the datasets used in the scientific literature on the Generalized Assignment Problem. The largest instances of the ...
- 2,495
5
votes
Assignment problem with batching costs
You can formulate this as an instance of the quadratic assignment problem by duplicating the workers and incurring the batching cost only for pairs of duplicate workers.
Here's an alternative MIQP ...
- 30.4k
5
votes
Accepted
Difficulties with finding equivalent problem on literature
I'm not 100% certain, but I think your problem is rather similar to a cutting stock problem. The routes represent "patterns", and the assignment of vehicles to routes is equivalent to choosing how ...
- 37.8k
5
votes
Accepted
Assignment problem using Hungarian method
I assume you're applying the matrix version of the algorithm.
When you happen to have only one $0$ for A and D the matrix is
\begin{align*}
\pmatrix{2&9&0&8&8\\2&1&6&0&...
- 2,705
5
votes
A Stack Overflow user's curious problem of maximising unsortedness
A first attempt is to model this problem using a special case of the Quadratic Assignment Problem (QAP), in which we want to assign URLs to positions in the permutation. To make the model smaller, we ...
5
votes
A Stack Overflow user's curious problem of maximising unsortedness
So, it turns out that this problem admits a linear-time exact algorithm!
The intuition is to add to the extremes (first and last position) two items with the same base $b^*$, which must be the base ...
- 2,073
5
votes
Use GA for Assignment Problem?
I agree with @RobPratt that a GA is not the ideal way to solve an assignment problem. The Wikipedia entry for assignment problems lists a few alternatives, and as Rob points out an LP solver should ...
- 37.8k
5
votes
Accepted
Expressing $\{0,1\}$ assignment across a matrix in MILP?
Okay...
$\sum_{i=1}^n V_{seat,i} \le seatvars_{seat} \quad \forall seat \in\ $seatVars
Looping 'for' in done by $\forall$
- 3,343
5
votes
Accepted
Minimize worker variance assignment problem
First, you might consider a different objective function. Rather than variance, you might minimize the maximum time spent by any worker, or minimize the range in worker times (the difference between ...
- 37.8k
5
votes
Minimize worker variance assignment problem
It depends what you mean by variance. Assuming it's how uniformly tasks are assigned and objective to have almost uniform total time per worker you either do what the above answer suggests or define ...
- 3,343
4
votes
Open Source MILP software for Python with user-friendly API to define the optimization problem
A more recent alternative is Python-MIP. It has built-in support of COIN-OR CBC. In addition, right now it supports one commercial solver, namely Gurobi. According to its website, it provides access ...
- 2,438
4
votes
Assignment Problem with Decreasing Costs
This reminds me a little of the maximum expected covering location model (MEXCLP) by Daskin (1983). The objective function depends nonlinearly on the number of facilities that cover each customer. ...
- 13.1k
4
votes
Assignment Problem With Weighted Bipartite Graph
From the comments I found that your problem can be described by
a setup time $s_j$ for process $j$
a travel time $c_{ij}$ for worker $i$ to process $j$
Then the waiting time that we get when ...
- 701
4
votes
Accepted
Assignment and scheduling problem with resource constraints
I didn't find a way to express the transition constraints so i give a description what this does and mention what it lacks.
...
- 3,975
4
votes
How to solve a minimum cost flow problem with time constraints
If I understand correctly, you can enforce the time constraint implicitly by omitting arcs. For each customer, there is a unique path by car and a unique path by bike. If the bike is too slow to ...
- 30.4k
4
votes
How to keep solutions stable/persistent in a problem with many equally good solutions?
Use worker/job identifiers to reproducibly perturb the objective function
If we didn't have to deal with possible changes to the problem, we could use a standard symmetry-breaking method: use a seeded ...
Only top scored, non community-wiki answers of a minimum length are eligible