LpVariable as Matrix

[Prituja A.V]

Hi,

I am trying to do a matrix multiplication - 3 x 3 matrix with 3 x 1 matrix and want the output to be stored in separate variable. I am not sure how to define the LpVariable to perform the matrix multiplication. 

Hope someone can help.

Do let me know if you need more information.

[Alexey Voevodkin]

Hi,

The code below may give you a hint but do no expect good performance if N>100.

---
import numpy as np

from pulp import *

N = 3

# matrix of LpVariables
a = LpVariable.matrix("a", ((i, j) for i in range(N) for j in range(N)))

# vector of numbers
b = np.arange(1, N+1)

a = np.array(a).reshape(N, N)

# matrix multiplication
tmp = np.dot(a, b)

for i in range(N):
    print(i, tmp[i])
---

Alexey

--
New posters to this group are moderated which can take up to 48 hours, so please be patient if your first post takes a while to turn up.
---
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discu...@googlegroups.com.
To post to this group, send email to pulp-or...@googlegroups.com.
Visit this group at https://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/d/optout.

[Prituja A.V]

Hi Alexey,

Thanks for the reply. I am working on a 3D bin packing problem (https://en.wikipedia.org/wiki/Bin_packing_problem). I am using Pulp and CPLEX solver. To give a summary, the objective is to minimise the unused volume within the container and I require the outputs to be the placement of the various parcels within the container. I am following the attached paper. 

My problem is - although I have added all the constraints, I get all the output as 0. I cannot find where the error is happening. I have attached my complete code. Is this something you can help with?

Highly appreciate any input provided. Thanks.

class Parcel:
    containers = 1
    parcels = 2
    conVolume = [540]
    parVolume = [60, 30]

    conWeight = [80]
    parWeight = [15, 10]

    conLength = [10]
    parLength = [4, 6]

    conWidth = [9]
    parWidth = [3, 5]

    conHeight = [6]
    parHeight = [5, 1]


def binpack(parcel):
    # Variable Decleration
    prob = LpProblem('BinPacking', LpMinimize)

    ps = [LpVariable("p{0}{1}".format(i + 1, j + 1), cat="Binary")
          for i in range(parcel.parcels) for j in range(parcel.containers)]
    print(ps)

    us = [LpVariable("u{0}".format(j + 1), cat="Binary") for j in range(parcel.containers)]
    print(us)

    # location of left bottom (x,y,z)
    xs = [LpVariable("x{0}".format(i + 1), lowBound=0, cat="Integer") for i in range(parcel.parcels)]
    # print(xs)

    ys = [LpVariable("y{0}".format(i + 1), lowBound=0, cat="Integer") for i in range(parcel.parcels)]
    # print(ys)

    zs = [LpVariable("z{0}".format(i + 1), lowBound=0, cat="Integer") for i in range(parcel.parcels)]
    # print(zs)

    # location of right top corner (x', y', z')
    rs = [LpVariable("r{0}".format(i + 1), lowBound=0, cat="Integer") for i in range(parcel.parcels)]
    # print(rs)

    ss = [LpVariable("s{0}".format(i + 1), lowBound=0, cat="Integer") for i in range(parcel.parcels)]
    # print(ss)

    ts = [LpVariable("t{0}".format(i + 1), lowBound=0, cat="Integer") for i in range(parcel.parcels)]
    # print(ts)

# for the overlapping constraint
    xik = [LpVariable("xik", cat="Binary")]
    yik = [LpVariable("yik", cat="Binary")]
    zik = [LpVariable("zik", cat="Binary")]
    xki = [LpVariable("xki", cat="Binary")]
    yki = [LpVariable("yki", cat="Binary")]
    zki = [LpVariable("zki", cat="Binary")]


#Objective function
    t = lpSum([us[i] * parcel.conVolume[i] for i in range(parcel.containers)]) - sum(parcel.parVolume)
    prob += t
    print(t)

  
# Dimension Constraint
    for i in range(parcel.parcels):
        t = (rs[i] - xs[i]) == parcel.parLength[i]
        prob += t
        print(t)

    for j in range(parcel.parcels):
        u = ps[j * parcel.containers: (j + 1) * parcel.containers]
        condition1 = sum([u1 * w for u1, w in zip(u, parcel.conLength)])
        # print(rs[j])
        t = rs[j] <= condition1
        prob += t
        print(t)

    for j in range(parcel.parcels):
        u = ps[j * parcel.containers: (j + 1) * parcel.containers]
        condition1 = sum([u1 * w for u1, w in zip(u, parcel.conWidth)])
        # print(rs[j])
        t = ss[j] <= condition1
        prob += t
        print(t)

    for j in range(parcel.parcels):
        u = ps[j * parcel.containers: (j + 1) * parcel.containers]
        condition1 = sum([u1 * w for u1, w in zip(u, parcel.conHeight)])
        # print(rs[j])
        t = ts[j] <= condition1
        prob += t
        print(t)

# Overlapping
    for i in range(parcel.parcels):
        if rs[i] <= xs[i + 1]:
            xik = 1
            xki = 0
        elif xs[i] < rs[i + 1]:
            xik = 0
            xki = 1
    print(xik, xki)

    for i in range(parcel.parcels):
        # for k in range(parcel.parcels):
        # u = bs[i * parcel.containers: (i + 1) * parcel.containers]
        if ss[i - 1] <= ys[i]:
            yik = 1
            yki = 0
        elif ss[i] < ys[i - 1]:
            yik = 0
            yki = 1
    print(yik, yki)

    for i in range(parcel.parcels):
        # for k in range(parcel.parcels):
        # u = bs[i * parcel.containers: (i + 1) * parcel.containers]
        if ts[i - 1] <= zs[i]:
            zik = 1
            zki = 0
        elif ts[i] < zs[i - 1]:
            zik = 0
            zki = 1
    print(zik, zki)

    li = []
    for j in range(parcel.parcels):
        u = ps[j * parcel.containers: (j + 1) * parcel.containers]
        # print(u)
        li.append(u)
    # print(li)

    r = []
    for i in range(parcel.containers):
        z = [x[i] for x in li]
        r.append(z)

    for i in range(0, len(r)):
        for j in range(0, len(r[i])):
            if j == len(r[i]) - 1:
                s = r[i][-1] + r[i][0]
            else:
                s = r[i][j] + r[i][j + 1]
            # print(s)
            t = xik + xki + yik + yki + zik + zki >= s - 1
            prob += t
            print(t)

    for i in range(parcel.containers):
        for j in range(parcel.parcels):
            a = rs[j - 1] <= xs[j] + (1 - xik) * parcel.conLength[i]
            b = xs[j] + 1 <= rs[j-1] + (xik * parcel.conLength[i])
            c = ss[j - 1] <= ys[j] + (1 - yik) * parcel.conWidth[i]
            d = ys[j] + 1 <= ss[j-1] + (yik * parcel.conWidth[i])
            e = ts[j - 1] <= zs[j] + (1 - zik) * parcel.conHeight[i]
            f = zs[j] + 1 <= ts[j-1] + (zik * parcel.conHeight[i])

            prob += a
            prob += b
            prob += c
            prob += d
            prob += e
            prob += f
            print(a, b, c, d, e, f)


binpack(parcel)

[Alexey Voevodkin]

Hi,

The code didn't work as it is.

I was able to get some feasible solution but it is still incorrect.

Jupyter notebook is attached.

I commented lines from your code and added mine like that
#for i in range(parcel.parcels):
for i in range(1, parcel.parcels):

Revise conditions b, d, e at the end.
For example in the condition b:

 b = xs[j] + 1 <= rs[j-1] + (xik * parcel.conLength[i])

I don't believe that it is xs[j] + 1.
It is either  xs[j+1] <= rs[j] + ....   or xs[j] <= rs[j-1] + ....

P.S.

I had to write in my last email that with PuLP your best friends are  LpVariable.dicts, LpSum, python loops and list comprehensions.

You are using the last three. Now try to use LpVariable.dicts