Skip to main content
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 ...
Kevin Dalmeijer's user avatar
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$...
Marcus Ritt's user avatar
  • 2,725
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 ...
prubin's user avatar
  • 39.3k
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,...
Sune's user avatar
  • 6,552
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
Lars H's user avatar
  • 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 ...
Mark L. Stone's user avatar
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 ...
prubin's user avatar
  • 39.3k
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
CMichael's user avatar
  • 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 ...
prubin's user avatar
  • 39.3k
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 ...
Erwin Kalvelagen's user avatar
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, ...
Sune's user avatar
  • 6,552
6 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 ...
prubin's user avatar
  • 39.3k
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
fontanf's user avatar
  • 2,623
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 ...
RobPratt's user avatar
  • 32.3k
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&...
Marcus Ritt's user avatar
  • 2,725
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 ...
Alberto Santini's user avatar
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 ...
prubin's user avatar
  • 39.3k
5 votes
Accepted

Adding linear penalties for multiple assignments

One possible approach is to define an increasing sequence of cost coefficients $c_{ij}^{(k)}$ representing the costs of assigning $i\rightarrow j$ a total of $k$ times. In the objective function, ...
prubin's user avatar
  • 39.3k
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$
Sutanu Majumdar's user avatar
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 ...
prubin's user avatar
  • 39.3k
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 ...
Ehsan's user avatar
  • 2,463
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. ...
LarrySnyder610's user avatar
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 ...
SimonT's user avatar
  • 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. ...
worldsmithhelper's user avatar
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
G_B's user avatar
  • 1,847

Only top scored, non community-wiki answers of a minimum length are eligible