11

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 this case, you won't have any problems when the number of areas is zero. It also makes the model linear instead of non-linear, which is usually a good thing. ...


10

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$, $w_{a2}=1$, $w_{b1}=100$, and $w_{b2}=2$. In this case matching $\{a2,b1\}$ of value $101$ is the only stable one but the minimum-weight matching is $\{a1,b2\...


9

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 job $i$; $d_{k}=$ discount factor for doing $k$ jobs ($d_{1}=1.0,d_{2}=0.95,\dots$); $N=$ total number of jobs to be assigned Binary variables: $x_{ijk}=1$ ...


9

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, and found that the most effective approach was to use exact knapsack separation from the capacity constraints. That is, I basically solved the dual of the "...


8

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 generally need to declare $x$ to be binary when you include side constraints.


8

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 vertices in the right position, ditto $\binom{n}{m}$ choices, and (iii) a bijection from the covered vertices on the left onto the covered vertices on the right, for ...


8

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 American, so you can call it the American algorithm.


7

I find Pulp is extremely easy to use, versatile and has good performance. Check it out here: https://pythonhosted.org/PuLP/solvers.html


7

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 would not need to worry about any syntax issues related to the solver.


6

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 worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker ...


6

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 make $c_{i2} > c_{i1}$ for all $i$. Since someone has to be assigned to sink 2, this effectively adds a constant amount $K$ to the objective function, and so ...


5

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 literature have $m = 80$ and $n = 1600$. Most algorithms designed for these instances won't be suitable for you. What seems the most relevant in your case are the ...


5

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 formulation that does not double the number of workers. Let binary decision variable $x_{i,j}$ indicate whether job $i$ is assigned to worker $j$. The problem ...


5

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 many times each pattern is cut. That last equivalence depends on vehicles being identical (any vehicle can handle any route, and the cost of the route is ...


5

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&5\\0&4&3&0&0\\4&8&0&12&6\\3&0&2&1&1} \end{align*} Now continue with Step 3: cover all zeros minimally, and ...


4

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 to advanced solver features like cut generation, lazy constraints, MIP starts and solution pools. Since Python-MIP is mentioned on the COIN-OR projects webpage, ...


4

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. Binary decision variables are used to count these assignments, similar to the $y_{jn}$ variables in @prubin's answer, and (again like in @prubin's answer), the ...


4

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 assigning worker $i$ to process $j$ is given by $w_{ij}:=|s_j-c_{ij}|$. Using $w_{ij}$ as your new weights of the assignments you can use any classic assignement ...


3

If the bipartite graph is $K_{n,n}$, then all $n$ vertices of the left hand size have exactly $n$ possible matches (each node of the right layer is a candidate). So the total number of matchings is $n^n$ indeed. Maybe you can try and detect if there are identical matchings among the $3174$ found by CPLEX ?


3

I didn't find a way to express the transition constraints so i give a description what this does and mention what it lacks. using JuMP using Gurobi #needs Gurobi license but any other MILP solver callable from JuMP should work too## Heading ## using UnicodePlots are dependencies. I used UnicodePlots for debugging. It is neat. In Julia dependencies can be ...


3

I think the problem is NP-hard since: it will reduce to the 0-1 Knapsack problem with an equality constraint; and, changing $\leq$ to $=$ in the 0-1 Knapsack constraint does not change its complexity (see explanation below). So, your problem is NP-hard as 0-1 Knapsack is. P.S. To see why (2) is correct, suppose all weights and values are equal. Then the ...


3

Minimizing the sum of all assignments: this is the classical version of the assignment problem. The Hungarian algorithm solves it in polynomial time. Minimizing the maximum of all assignments: this one is known as the linear bottleneck assignment problem. The most obvious way to solve it is to solve a succession a decision problems: is it possible to find ...


3

I tried to find the below-cited paper to read and answer your question but unfortunately, I couldn't find that. Anyway, in this paper, the authors investigated VRPPDTW (Vehicle Routing Problem with Pick up and Delivery with Time Windows) and proposed an exact algorithm (there are also some heuristic and metaheuristic approaches to solve this type of VRPs) to ...


3

AFAIK, one of an efficient way to solve Generalized Assignment Problem (GAP), is using Branch and Price technique. I will hope, this or this link be useful.


3

You could try using the greedy heuristic to get an initial solution and then try out one of the many neighborhood-search type metaheuristics. I mentioned sorting on $p_{ij}$ in a comment, but it might (or might not) be better to sort on $p_{ij}/w_{ij}$ (or, time permitting, try both and pick the better solution). For improving on the starting solution, GRASP ...


2

int nbPilots = 50; int nbLocations = 7; int nbDays = 30; range pilots = 1..nbPilots; range days = 1..nbDays; range locations = 1..nbLocations; //decision variable/ dvar boolean assign [pilots][days][locations] ; dvar boolean rest [pilots][days][locations]; //objective/ minimize sum(i in pilots, j in days, l in locations)assign[i][j][l]; //...


2

As suggested above, PULP is one of the open source solver. Apart from this, the best MILP solver available in open source is preferably offered in SCIP optimization suite. I think Google OR tools are built using SCIP only. Moreover, you can refer to COIN-OR where researchers from ORMS society have maintained their projects.


2

When you have two objective functions, and your client can't articulate exactly how the two are to be weighed against one another, sometimes the easiest solution is to avoid making that decision. Instead of trying to figure out the client's priorities and find the single best solution, you can present them with a small list of options guaranteed to contain ...


2

In your greedy algorithms you are assigning $n-1$ people to jobs by for _ in range(n - 1). Thus you are assigning one job too little - even though this choice is trivial it is missing in your objective. When fixing it to $n$ this should solve your problem. Just because I couldn't resist not mentioning it. There are extremely good polynomial time exact ...


2

First, let's split this into two separate problems: making the initial assignments; and updating assignments over time. (If you already have assignments in place, you may only need the second problem.) The initial problem can be modeled a generalized assignment problem (GAP). Technically this is an integer linear program, with a zero-one variable for each ...


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