# Tag Info

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 ...

### 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$...

### 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 ...

### 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,...
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 ...

### 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 ...
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 ...
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 ...
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

### 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 ...

### 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 ...

### 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, ...
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 ...

### 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$ ...
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 ...

### 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 ...
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 ...
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&...

### 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 ...

### 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 ...

### 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 ...
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$
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 ...

### 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 ...

### 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 ...

### 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. ...

### 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 ...
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. ...