3
$\begingroup$

I have a quadratic model of parking $N$ cars in $S$ separate lanes as follows. Each car has an arrival time and a departure time. Departure follow the last in first out principle. The objective is to minimize the number of maneuvers.

Indices:
car indices: $i,j \in \{1,\dots,N\}$,
lane indices: $m \in \{1,\dots,S\}$

Parameters:
$c_{ij} = \begin{cases} 1, &\text{If parking car $i$ and $j$ in the same lane will cause a maneuver when departing} \\ 0, &\text{otherwise} \end{cases} $

Decision variables:
$x_{im} = \begin{cases} 1, & \text{If car $i$ is parked in lane $m$} \\ 0, & \text{otherwise} \end{cases}$

\begin{align} \text{QM}\hspace{1cm} & \min{\sum_m^S \sum_{i=1}^{N-1}\sum_{j=1+1}^{N} c_{ij} x_{im} x_{jm}} \\ \text{Subject to}\\ \sum_{m=1}^{S}{x_{im}} &=1 & \forall\ & i \\ x_{im} & \in \{0,1\} & \forall\ & i,m \end{align}

I have the linearized model LQM1 of QM as follows:

Derived variables:
$z_{ij} =\begin{cases} 1, &\text{if cars $i$ and $j$ are parked in the same lane}\\ 0, &\text{otherwise} \end{cases}$

\begin{align} & \text{LQM1} & \min{\sum_{i=1}^{N-1}\sum_{j=1+1}^{N} c_{ij} z_{ij}} \\ \text{Subject to}\\ \sum_{m=1}^{S}{x_{im}} &=1 & \forall\ & i \\ x_{im} + x_{jm} & \leq z_{ij} + 1 & \forall\ & i,j,m, i < j \\ z_{ij} & \geq 0 & \forall\ & i,j, i < j \\ x_{im} & \in \{0,1\} & \forall\ & i,m \end{align}

In the linearized model LQM1, $z_{ij}$ does not need a binary restriction because $c_{ij}$ is nonnegative and the objective function is minimized.

My concern is what is the difference if I have solved LQM2 instead of LQM1 with Gurobi? Is there a theoretical reason when linearizing the quadratic model?

\begin{align} & \text{LQM2} & \min{\sum_{i=1}^{N-1}\sum_{j=1+1}^{N} c_{ij} z_{ij}} \\ \text{Subject to}\\ \sum_{m=1}^{S}{x_{im}} &=1 & \forall\ & i \\ x_{im} + x_{jm} & \leq z_{ij} + 1 & \forall\ & i,j,m, i < j \\ x_{im} & \in \{0,1\} & \forall\ & i,m \\ z_{ij} & \in \{0,1\} & \forall\ & i,j \end{align}

$\endgroup$
1
  • 1
    $\begingroup$ As MIP solvers have so many moving parts, these things are very difficult to predict. In my opinion, it is best to just try things out. (Afterwards, we can invent an explanation that sounds reasonable). $\endgroup$ – Erwin Kalvelagen Jun 19 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.