Solver is not convering

Question

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

Answer 1

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.

Answer 2

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$