# Solver is not convering

I have cars and persons and I want each persons to be in a car. Moreover, each person has a number of persons they can share a car with.

I have implemented a model (with binary variables and constant objective) which works well for small instances. However for larger ones the solver takes ages and I have to interupt it.

What would be a good approach to takle this issue (I'm thinking branch-and-bound, metaheuristics, etc. But I don't really have a clear idea).

• Is $M_i$ the maximum number of persons with whom $i$ can share a car (as opposed to minimum or exact number), and does it include $i$ or not (i.e., if $M_i=3$ is that $i$ and two others or $i$ and three others)? Also, do cars have capacity limits separate from $M_i$?
– prubin
Mar 15 at 15:43
• Are the $n$ cars identical? Mar 15 at 15:55
• @RobPratt Yes the cars are identical
– Meth
Mar 15 at 17:22
• Column generation might work well here. Are you able to share data for a larger instance? Mar 15 at 17:27
• @Meth what's the objective here? If it's to accommodate all m passengers & if n cars are identical then heuristic involving sorting will do the job. Mar 15 at 18:12

The following solves quickly with at least one commercial solver. Let binary decision variable $$x_{ij}$$ indicate whether person $$i$$ rides in car $$j$$. The constraints are: \begin{align} \sum_j x_{ij} &= 1 &&\text{for all i} \tag1\label1 \\ \sum_{k\not= i} x_{kj} + (m - 1 - M_i) x_{ij} &\le m - 1 &&\text{for all i and j} \tag2\label2 \end{align} Constraint \eqref{1} assigns each person to exactly one car. Constraint \eqref{2} enforces the logical implication $$x_{ij} = 1 \implies \sum_{k\not= i} x_{kj} \le M_i,$$ which you could instead enforce via an indicator constraint.

An interesting variant would be to minimize the number of cars used. In that case, introduce a binary variable $$y_j$$ to indicate whether car $$j$$ is used, change the RHS of \eqref{2} to $$(m-1)y_j$$, and minimize $$\sum_j y_j$$.

This formulation lends itself to column generation with a set partitioning master problem, and Ryan-Foster branching can perform well. That approach is automated in SAS if you specify to use the Dantzig-Wolfe decomposition algorithm with METHOD=SET or explicitly identify the block structure via the .BLOCK constraint suffix. If you are using a different solver, you can try implementing column generation yourself. The corresponding formulation has a binary decision variable $$z_S$$ for each feasible subset $$S$$ of (at most $$4$$) people. The constraints are then: \begin{align} \sum_{S: i \in S} z_S &= 1 && \text{for all i} \tag3\label3 \\ \sum_{S} z_S &\le n \tag4\label4 \end{align} Constraint \eqref{3} assigns each person to exactly one car. Constraint \eqref{4} enforces using at most $$n$$ cars. For static column generation, you would generate all feasible $$S$$ a priori and solve one MILP. For dynamic column generation, you would need to iterate between a master LP problem and a MILP subproblem.

• Are you minimizing the number of cars used or just trying to find a feasible solution? Mar 15 at 18:59

You can try the following algorithm:

1. Sort passengers in descending order of number of co-passengers, $$M_i$$.Output sets $$S_4 = \{i\in P: M_i \gt 3\}$$. Similarly sets $$S_3, S_2, S_1, S_0$$. P is set of $$m$$ passengers\
2. Loop through each of the sets in the cardinal number $$4,3,2,1$$ like
initialize $$C_1 = 0$$
$$C_{n} = C_{n} + i: i \in S_{k+1|k\lt 4} \land m_i \lt C_{j}$$
$$C_{n} = k \quad \forall n \le {\vert S_k\vert\over k}$$
You can allocate/track individual allocation as well
$$C_{n}= \{i: i \in S_k\}: C_n \lt k \quad \forall n \le {\vert S_k\vert\over k}$$
$$C_{n+1} = {\vert S_{k} \vert \mod k}$$
$$\forall n \in$$ cars:
$$\forall k \in \{4,3,2,1,0\}$$ (Nested loop, $$n$$ is the inner loop)

$$C_j =$$ number of passengers in car $$j$$

• Basically you collect members who say are ok to travel in group of 4, in a set $S_4$. Suppose its 7 people. So you would need 1 car (4)+1car(3). Allocate 4 people to first car, then 3 to next car. Then move to next set $S_3$. If $S_4$ has 9 people, you'd need 2 cars and 1 car to get 9th passenger from $S_4$ and then 2 more to same car from $S_3$. Since cars are identical and different solutions as only constraint is how many co-passengers each passenger is ok with, you may not need a solver. Mar 16 at 17:42