dfs

commit 79b28adafc1d5743e7c3cb6bacb39ed31b6732bb (HEAD -> main)
Author: Fabrice Frachon <fabricfr@microsoft.com>
Date:   Mon Feb 15 21:46:47 2021 -0800

    First version of ship loading in PUBO format

diff --git a/samples/multiship-loading-sample/multiship-loading-sample.py b/samples/multiship-loading-sample/multiship-loading-sample.py
new file mode 100644
index 0000000..675ccd1
--- /dev/null
+++ b/samples/multiship-loading-sample/multiship-loading-sample.py
@@ -0,0 +1,273 @@
+#!/usr/bin/env python
+# coding: utf-8
+# Copyright (c) Microsoft Corporation.
+# Licensed under the MIT License.
+
+
+#  In this example, we will take our learnings from the ship-loading sample and generalize the load balancing
+#  between two ships to the load-balancing between multiple-ships.
+# 
+#  For this sample, we will use a PUBO format that assumes indices are either 0 or 1 (instead of -1 / 1 for Ising)
+# 
+#  In order to balance containers between multiple ships, one option is to define a cost function that:
+#       1. Penalizes variance from a theoretical equal distribution (EqDistr = TotalContainerWeights / NbShips)
+#       2. Penalizes the assignment of the same container on multiple ships
+#
+#   We will create two cost-functions H1 and H2 that we will then sum to evaluate the total cost of a solution
+# 
+#  1. Penalize variance from equal distribution between ships
+#     A way to penalize a large variance from the equal distribution for a given ship is to express it in the following way:
+#       Given 3 containers with respective weights W0, W1, W3 and EqDistrib = (W0 + W1 + W2) / 3
+#           (W0 + W1 + W2 - EqDistrib)^2
+# 
+#   Let's take the following example:
+# 
+#   Cont. weights       1 5 9 7 3
+#   Total weight        25
+#   Ships               A, B, C
+#   EquDistrib          25 / 3 = 8.33
+
+#                   Containers
+#                   1 5 9 7 3
+#   Ship
+#   A               0 0 9 0 0   (9-8.33 ) ^2    = 0.4489
+#   B               0 5 0 0 3   (5+3-8.33)^2    = 0.1089
+#   C               1 0 0 7 0   (1+7-8.33)^2    = 0.1089
+#
+#   As we need to represent our problem in a binary format we need to "encode" the presence xi=1 or absence xi=0 of a given container for every single ship.
+#       Using the example above, we duplicate the list of container weights for each ship into a single list of weights:
+#           1  5  9  7  3  - 1  5  9  7  3  - 1   5   9   7   3
+#           W0 W1 W2 W3 W4   W5 W6 W7 W8 W9   W10 W11 W12 W13 W14 
+# 
+#       The cost function H1 becomes: 
+#           H1 = (W0.x0 + W1.x1 + W2.x2 + W3.x3 + W4.x4 - EqDistrib)^2                          --> For Ship A
+#               + (W5.x5 + W6.x6 + W7.x7 + W8.x8 + W9.x9 - EqDistrib)^2                         --> For Ship B
+#                   + (W10.x10 + W11.x11 + W12.x12 + W13.x13 + W14.x14 - EqDistrib)^2           --> For Ship C
+# 
+#       If you expand the above and group the common terms, you get the following:
+#           W0^2.x0^2 + W1^2.x1^2 + + W2^2.x2^2 + .... + W14^1.x14^14                           --> Term(w=Wi^2, indices=[i,i]
+#               + 2(W0.x0 * W1.x1) + 2(W0.x0 * W2.x2) + 2(W0.x0 * W2.x2) + 2(W0.x0 * W4.x4)     --> Term(w=2*Wi*Wj, indices=[i,j])
+#                   + 2(W1.x1 * W2.x2) + 2(W1.x1 * W3.x3) + 2(W1.x1 * W4.x4)
+#                       + 2(W2.x2 * W3.x3) + 2(W2.x2 * W4.x4)
+#                           + 2(W3.x3 * W14.x14)
+#               + 2(W5.x5 * W6.x6) + 2(W5.x5 * W7.x7) + 2(W5.x5 * W8.x8) + 2(W5.x5 * W9.x9)
+#                   + ...
+#                       + ...
+#                           + ...
+#               + ...
+#           - (W0.x0 * EqDistrib) - (W1.x1 * EqDistrib) - ... - (W14.x14 * EqDistrib)          --> Term(w=-2*Wi*EqDistrib, indices=[i])
+# 
+#  2. Penalize the assignment of the same container on multiple ships
+#           Using the containers weight encoding in #1, we can devise a cost function such as this one for the first container:
+#              (W0.x0 + W5.x5 + W10.x10 - W0)^2 
+#           As W0, W5 and W10 are actually the same value (it is the same container represented across multiple ships)
+#           The following is the equivalent: (W0.x0 + W0.x5 + W0.x10 - W0)^2
+# 
+#           If we expand and group the common terms, you get the following:
+#               W0^2.x0^2 + W0^2.x5^2 + W0^2.x10^2
+#                   + 2(W0^2.x0.x5) + 2(W0^2.x0.x10) + 2(W0^2.x5.x10)
+#                       - 2(W0^2.x0) - 2(W0^2.x5) - 2(W0^2.x10)
+#                           + W0^2
+# 
+#           And you repeat the above for each container across all ships
+#               H2 = W0^2.x0^2 + W1^2.x1^2 + .... + W14^2.x14^2                                --> Term(w=Wi^2, [m,m])
+#                   + 2(W0^2.x0.x5) + 2(W0^2.x0.x10) + 2(W0^2.x5.x10) + ....                   --> Term(w=2*Wm^2, [m,n])
+#                           + 2(W4^2.x4.x9) + 2(W4^2.x4.x14) + 2(W9^2.x9.x14)
+#                   - 2(W0^2.x0) - 2(W1^2.x1) - .... - 2(W14^2.x14)                            --> Term(w=-2*Wm^2, [m])
+#                           + W0^2
+# 
+#   You will notice that H1 and H2 have common indices [i,i]/[m,m] and [i]/[m]
+#   We will need to be careful to not duplicate them in our final list of Terms describing the cost function.
+#   H = H1 + H2
+#     = 2 * (W0^2.x0^2 + W1^2.x1^2 + .... + W14^2.x14^2)                                        --> Term(w=2*Wi^2, [i,i])
+#       - 2(W0^2.x0) - .... - 2(W4^2.x14) - (W0.x0 * EqDistrib) - ... - (W14.x14 * EqDistrib)   --> Term(w=-2Wi^2 - W0*EqDistrib, [i])
+#                   + 2(W0^2.x0.x5) + 2(W0^2.x0.x10) + 2(W0^2.x5.x10) + ....                    --> Term(w=2*Wm^2, [m,n])
+#                           + 2(W4^2.x4.x9) + 2(W4^2.x4.x14) + 2(W9^2.x9.x14)
+
+# Instantiate Workspace object which allows you to connect to the Workspace you've previously deployed in Azure.
+# Be sure to fill in the settings below which can be retrieved by running 'az quantum workspace show' in the terminal.
+from azure.quantum import Workspace
+
+# Copy the settings for your workspace below
+workspace = Workspace (
+    subscription_id = "",  # Add your subscription_id
+    resource_group = "",   # Add your resource_group
+    name = "",             # Add your workspace name
+    location = ""          # Add your workspace location (for example, "westus")
+)
+
+workspace.login()
+
+# Take an array of container weights and return a Problem object that rep