4 votes

Google-OR Tools: Assignment minimizing overlapping members

The MIP model by Erwin Kalvelagen is a good way to solve the problem, and is probably quite efficient. As an alternative, the following MiniZinc model is a fairly straight-forward model based on the ...
Zayenz's user avatar
  • 196
3 votes

How to represent the objective function of the Weapon Target Assignment problem in CVXPY?

Now $$ \begin{array}{rcl} t_j & \geq & \prod_{i=1}^m (1-p_{ij})^{x_{ij}} \\ & = & exp(\ln(\prod_{i=1}^m (1-p_{ij})^{x_{ij}})) \\ & = & exp(\sum_{i=1}^m x_{ij} \ln(...
ErlingMOSEK's user avatar
  • 3,101
3 votes

How to represent the objective function of the Weapon Target Assignment problem in CVXPY?

TLDR: This can be formulated and solved in CXVPY with Mosek as solver, as a Mixed-Integer (generalized) Geometric Programming problem, using CVXPY's Disciplined Geometric Programming (DGP) capability. ...
Mark L. Stone's user avatar
3 votes
Accepted

Modeling: How to force customers visit their NEAREST facility

If the objective is to minimize total distance, this will happen naturally. But if you want to explicitly enforce it, you can impose a rule like $$\lnot(y_{ni} \land v_j) \quad \text{for all $n,i,j$ ...
RobPratt's user avatar
  • 31.5k
3 votes
Accepted

Assignment Problem - Students and teachers

As in the comments: as it stands, the problem is infeasible. For student 3, they could never be given a class with any teacher, because they have never had at least two classes with any teacher. You ...
Reinderien's user avatar
3 votes
Accepted

Google-OR Tools: Assignment minimizing overlapping members

It is often a good idea to split this task into two parts: Developing a mathematical model Implement the model (coding) Often, if you do a good job on (1), (2) becomes a breeze. Here is my attempt. ...
Erwin Kalvelagen's user avatar
3 votes

Optimizing Storage Allocation and Supply for Manufacturing with Time Constraints

I guess, as you correctly mentioned, this problem is too complex as actually many of the SCM problems are complex and I doubt one math formulation can handle all of its aspects. Instead, the problem ...
A.Omidi's user avatar
  • 8,717
2 votes

Modeling: How to force customers visit their NEAREST facility

If you would like to assign the customers to the nearest facility, one way would be by adding a set-covering constraint to ensure the customers with the minimum distance from a facility are assigned ...
A.Omidi's user avatar
  • 8,717
2 votes
Accepted

PuLP ensure first and last choice

Additional constraints $ \sum_{k=1}^{t-1} x_{l,k} \le 1-x_{a,t} \quad \forall l \neq a$ $\sum_{k=t+1}^{T} x_{l,k} \le 1-x_{d,t} \quad \forall l \neq d$ where $x$ is the binary location pair variable ...
Sutanu Majumdar's user avatar
2 votes
Accepted

Effective methods for solving the assignment and packing problem

I don't think the following heuristic can be said to "guarantee near-optimal solutions", but it is quite straightforward to code and can make efficient use of parallel threading/multiple ...
prubin's user avatar
  • 38.8k
2 votes
Accepted

Assignment of colored boxes to groups

Here's a mixed integer linear programming formulation that I used to find an optimal solution with objective value $1506$ for your $10 \times 9$ instance. Let $(c_{ij})$ be the given (sparse) cost ...
RobPratt's user avatar
  • 31.5k
1 vote

iterative geographic assignment problem

The urbanization part is easy. Fix $x_{vc}=0$ for all $(v,c)$ combinations that do not satisfy the urbanization constraint (either by adding an equation or simply by not including those variables in ...
prubin's user avatar
  • 38.8k
1 vote

Google-OR Tools: Assignment minimizing overlapping members

The original data mises the team 9,16 (these two do not belong to any team) The code in OR-TOOLS Data ...
Optimization team's user avatar
1 vote
Accepted

Formulating assignment problem with people attributes that need to be balanced per assignment attribute in or-tools, CP-sat

You'd need two optimization variables Binary $ x_{s,r} = 1$ if student $s$ from set A is matched with row $r$ from set B Binary $ y_{s,c} = 1$ of student is matched to a class $c$ Derived sets/matrix ...
Sutanu Majumdar's user avatar
1 vote

Modeling: How to force customers visit their NEAREST facility

Another way is for all customers $n$ sort the distance in ascending order into a set $S_n =\{d_{ni}: d_{n,i} \le d_{n,i+1}\}$ basically indexed by the facility. Then for each customer loop the below ...
Sutanu Majumdar's user avatar
1 vote
Accepted

Assignment problem with multiple precedence constraints

The following assumes that the $(v,u)\in A$ precedence requirements have to do with the order cars are in a row and not something else (such as cars before trucks, heavy vehicles before light vehicles ...
prubin's user avatar
  • 38.8k
1 vote

Is there a name for this variation of the generalized assignment problem?

The problem sounds like a parallel resource scheduling problem with preemption. One of the efficient way to solve the problem (as an LP) is to define that as a bipartite graph in which the first group ...
A.Omidi's user avatar
  • 8,717
1 vote

Is there a name for this variation of the generalized assignment problem?

It's similar to knapsack problem. I am referring to wiki links here from here you can refer to other additional academic papers. Also check this general wiki as well on general assignment problem. ...
Sutanu Majumdar's user avatar
1 vote

PuLP ensure first and last choice

Here’s a somewhat automated way to obtain the formulation proposed by @Sutanu. You want to enforce the logical implication $$\bigwedge_t \left(x_{at} \implies \bigwedge_{l\not= a}\bigwedge_{k<t}\...
RobPratt's user avatar
  • 31.5k
1 vote

PuLP ensure first and last choice

For anyone who comes across this in the future and is looking to translate the solution @Sutanu posted to PuLP, here is how I implemented it. ...
3Li's user avatar
  • 35
1 vote
Accepted

Alternative Approaches to Assignment Problem

If you are open to heuristic (approximate) solutions, one possibility is to generate a set of routes and then rewrite the problem to assign trucks and customers/orders to routes. In problems of this ...
prubin's user avatar
  • 38.8k
1 vote

Alternative Approaches to Assignment Problem

It seems that you are trying to solve a pickup and delivery problem. MIP solvers are often not the best tool for that, and getting good results with them requires special models and tricks. There are ...
Ggouvine's user avatar
  • 1,867

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