The Airbus Quantum Computing Challenge is a set of problems from Airbus where the challenge is to implement the solutions on a quantum computer. This project looks specifically at Problem Statement 5: Aircraft Loading Optimisation. This solver currently does not work with IE or Edge. The server is only one vCPU, with 3 gevent workers, but it still manages the example optimisations with relative ease.
There are currently two linear programs. The notation and labels are consistent between the linear programs. The total number of blocks being considered is $n$, although the solution will only have $N$ blocks. The length of the fuselage is $L$, this is in units of type 1 cargo blocks. The maximum payload of the fuselage is $W_p$. The index $i$ indicates a cargo block, so $s_i$ is the size of block $i$, and $m_i$ is the mass of block $i$. $s_i$ can be $0.5$, $1$ or $2$. $b_i$ is $1$ if block $i$ is in the fuselage and $0$ if block $i$ is not in the fuselage. The index $j$ indicates a section of the fuselage, so $j$ goes from $1$ to $L$.
The first linear program is significantly simpler than the second and therefore runs very quickly. It takes the list of all available cargo blocks and returns the subset of cargo blocks which maximises the mass of the cargo blocks without exceeding the maximum weight limit or the length of the fuselage.
$$ \textrm{maximise} \quad \sum_{i=1}^{n}m_ib_i \\ \textrm{subject to} \quad \sum_{i=1}^{n}m_ib_i \leq W_p , \\ \textrm{and} \quad \sum_{i=1}^{n}s_ib_i \leq L $$
In words, we want to maximise the mass of the blocks in the fuselage by summing the mass of all the blocks which appear in the fuselage. This is subject to the constraints that the mass of all the blocks that appear in the fuselage is less than the maximum payload, and also that the size of all the blocks that appear in the fuselage is less that the length.
The second linear program is more complicated as we have to fit the blocks into the fuselage such that the centre of gravity is in the middle (this could also be set to an arbitrary position). The linear program involves introducing a matrix, $x_ij$, which is 1 if block $i$ is in sections $j$, and 0 otherwise. This means two blocks can have the same $j$ index if they are both size 0.5. A block of size 2 is in both section $j$ and $j+1$. The resulting linear program is:
$$ \textrm{minimise} \quad \sum_{i,j}x_{ij}m_j\left(j-\tfrac{L-1}{2}\right) \left[1-\tfrac{1}{3}\left(s_i-\tfrac{1}{2}\right)\left(s_i-1\right)\right] \\ \textrm{subject to constraints, 1): } \sum_{i,j}x_{ij}m_j\left(j-\tfrac{L-1}{2}\right) \left[1-\tfrac{1}{3}\left(s_i-\tfrac{1}{2}\right)\left(s_i-1\right)\right] \geq 0 \\ \textrm{and 2) for all fuselage sections (j): } \sum_{i=1}^{n}x_{ij}\left[s_i-\tfrac{2}{3}\left(s_i-\tfrac{1}{2}\right)\left(s_i-1\right)\right] \leq 1 \\ \textrm{and 3) for all cargo blocks (i): } \sum_{j=1}^{L}x_{ij} - s_i - \tfrac{2}{3}\left(1-s_i\right)\left(2-s_i\right)= 0 \\ \textrm{and 4) for all size 2 cargo blocks (i): } \sum_{j=1}^{L}x_{ij}j(-1)^j \leq 1 \quad \textrm{and} \quad \sum_{j=1}^{L}x_{ij}j(-1)^j \geq -1 $$
We want to minimise the torque around the centre position, so this is minimising the sum of the torque of all the individual blocks where the torque is the mass of block $i$ if $i$ is in position $j$ around the centre point. The last term gives $0.5$ if the block is size 2. This is because blocks of size 2 are in two positions. The contraints can be described as follows:
We need to map our linear programs to QUBO (quadratic unconstrained binary optimisation) problems. This makes the problems suitable for a quantum annealer such as the D-Wave machine.
We start with a linear program of the form in step one:
$$ \textrm{maximise} \quad \sum_{i=1}^{n}m_ib_i \\ \textrm{subject to} \quad \sum_{i=1}^{n}m_ib_i \leq W_p , \\ \textrm{and} \quad \sum_{i=1}^{n}s_ib_i \leq L $$
Which can be written
$$ \textrm{maximise} \quad \vec{m} \cdot \vec{b} \\ \textrm{subject to} \quad \mathbf{B} \vec{b} \leq \vec{c} $$
where $\vec{b}$ is a vector of $b_i$, $\vec{m}$ is a vector of $m_i$, and $\vec{c}=\left(W_p~L\right)^{\intercal}$. Using slack variables we can turn the inequality into an equality. This means we now have
$$ \textrm{maximise} \quad \vec{x}^{\intercal} \mathbf{C} \vec{x} \\ \textrm{subject to} \quad \mathbf{A} \vec{x} = \vec{c} $$
With $\vec{b}$ extended by slack variables, giving $\vec{x}$, a vector of binary variables, $x_i \in \{0, 1\}$. To accomodate the slack variables we extend the matrix $\mathbf{B}$ to $\mathbf{A}$, where the coefficients of the slack variables are powers of 2 in order to span the set of numbers up to the limit of the constraint. We can now recast the problem as a quadratic unconstrained binary optimisation problem.
$$ y = \vec{x}^{\intercal} \mathbf{C} \vec{x} + P \left(\mathbf{A} \vec{x} - \vec{c}\right)^{\intercal}\left(\mathbf{A} \vec{x} - \vec{c}\right)$$ $$ y = \vec{x}^{\intercal} \mathbf{C} \vec{x} + P \left(\vec{x}^{\intercal} \mathbf{A}^{\intercal} - \vec{c}^{\intercal}\right)\left(\mathbf{A} \vec{x} - \vec{c}\right)$$ $$ y = \vec{x}^{\intercal} \mathbf{C} \vec{x} + P \left(\vec{x}^{\intercal} \mathbf{A}^{\intercal}\mathbf{A} \vec{x} - \vec{x}^{\intercal} \mathbf{A}^{\intercal} \vec{c} - \vec{c}^{\intercal}\mathbf{A} \vec{x} \right) + P\vec{c}^{\intercal}\vec{c}$$ $$ y = \vec{x}^{\intercal} \mathbf{C} \vec{x} + \vec{x}^{\intercal} \mathbf{D} \vec{x} + \textrm{constant}$$ $$ y = \vec{x}^{\intercal} \mathbf{Q} \vec{x} + \textrm{constant}$$
This means we can compute $\mathbf{Q}$ using $$\mathbf{D} = P\left(\mathbf{A}^{\intercal}\mathbf{A} - \mathrm{diag}\left(\mathbf{A}^{\intercal} \vec{c}\right) - \mathrm{diag}\left(\vec{c}^{\intercal}\mathbf{A}\right)\right)$$ $$\mathbf{D} = P\left(\mathbf{A}^{\intercal}\mathbf{A} - 2\mathrm{diag}\left(\mathbf{A}^{\intercal} \vec{c}\right)\right) $$ For references for the approach used see: