2
$\begingroup$

I have read the paper of Haase and Muller (2014) where they present the linear reformulations of the multinomial logit choice probabilities and compare different approaches. I have tried for an exercise to code their models, particularly the variant of Haase (2009), and to solve it with Gurobi 6.5. The issue is that I obtain really long running times.

In their numerical investigation they used CPLEX 12 on a 64-bit Windows Server 2008 with 1 Intel Xeon 2.4 GHz processor and 24 GiB of RAM. On the other hand I am using Python + Gurobi on a 64-bit Windows 8 with 2 Six-Core AMD Opteron 2.00 GHz processors and 32 GiB of RAM.

I understand that there can be differences between Gurobi and CPLEX in running times on different models/programs. In some cases the Gurobi is better, and in some cases the CPLEX is better. Also, I understand that my machine is not very representative and I hope that 0.4 GHz doesn't make such a big difference. But the difference is really huge. For some small problems, that Haase and Muller needed a little bit more than a minute to solve them, on my machine I need more than two hours. Is it possible that choice of the solver and machine can matter that much? Can someone, please, check my code, because I am newbie in this game.

This is the mathematical model written in LaTeX:

$ \max F = \sum_{i\in I} \sum_{j\in J} x_{ij} $

s.t.

$ \sum_{j\in J} y_j = r $

$ \tilde{x}_{i} + \sum_{j\in J} \leq 1, \forall i \in I $

$ x_{ij} - \frac{\phi_{ij}}{1 + \phi_{ij}} y_j \leq 0, \forall i \in I, j \in J $

$ x_{ij} - \phi_{ij}\tilde{x}_i \leq 0, \forall i \in I, j \in J $

$ y_i \in \{0, 1\}, \forall j \in J $

$ x_{ij} \geq 0, \forall i \in I, j \in J $

$ \tilde{x}_i \geq 0, \forall i \in I $

where $ \phi_{ij} = \frac{ e^{v_{ij}} }{\sum_{k\in M\setminus J} e^{v_{ik}}} $.

Here is the code in Python.

from gurobipy import *
import math
import numpy as np

n = 200 # The number of customers
m = 60 # The number of possible facility locations.
x_coords = 30 * np.random.random_sample(n + m)
y_coords = 30 * np.random.random_sample(n + m)
I = { i: (float(x_coords[i]), float(y_coords[i])) for i in range(n) } # The customers' locations.
M = { j: (float(x_coords[n + j]), float(y_coords[n + j])) for j in range(m) } # The possible facility locations.
J = {i: M[i] for i in range(m-10)} # J is subset of M. The competitor has located facilities in M\J.
MdiffJ = {i: M[m-10+i] for i in range(10)} # Competitor's facility locations. |M\J| = 10 as in the paper.
d = {}
v = {}
for i in I:
    for j in J:
        d[i,j] = abs(I[i][0] - J[j][0]) + abs(I[i][1] - J[j][1]) # Rectangular distances.
        v[i,j] = -0.2 * d[i,j]
r = round(0.2 * len(J)) # == 0.2 * |J|, as in the paper.


model = Model()

# Creating variables
y = {}
x_tilda = {}
x = {}
for j in J:
    y[j] = model.addVar(vtype=GRB.BINARY, name="y_%i" % j)
for i in I:
    x_tilda[i] = model.addVar(lb=0, name="x_tilda_%i" % i)
    for j in J:
        x[i,j] = model.addVar(lb=0, name="x_%i%i" % (i,j))

# Integrating variables
model.update()

# Setting the objective.
obj = LinExpr()
obj += quicksum(quicksum(x[i,j] for j in J) for i in I)

# Setting the objectiv as a maximization problem.
model.setObjective(obj, GRB.MAXIMIZE)

# Computing phi (constants)
phi = {}
for i in I:
    for j in J:
        phi[i,j] = math.e**v[i,j] / (sum(math.e**v[i,k] for k in MdiffJ))

# Adding constraints.
model.addConstr(quicksum(y[j] for j in J) - r == 0, "sum(y_*) == r")
for i in I:
    model.addConstr(x_tilda[i] + quicksum(x[i,j] for j in J) <= 1, "x_tilda_%i+sum(x_%i*) <= 1" % (i,i))
    for j in J:
        model.addConstr(x[i,j] - (phi[i,j] / (1 + phi[i,j])) * y[j] <= 0, "x_%i%i - frac * y_%i <= 0" % (i,j,j))
        model.addConstr(x[i,j] - phi[i,j] * x_tilda[i] <= 0, "x_%i%i - phi_%i%i * x_tilda_%i <= 0" % (i,j,i,j,i))

# Computing the optimal solution.
model.optimize()
$\endgroup$
4
  • $\begingroup$ The solver can certainly make a difference and I suspect that is the main time difference you are seeing. Why the two solvers are so different in run times is a curious thing, however. $\endgroup$
    – spektr
    May 1 '16 at 0:06
  • $\begingroup$ @choward Well that's a sad new in some sense. So, basically, there is nothing wrong with my code? $\endgroup$
    – DDCh
    May 1 '16 at 5:23
  • $\begingroup$ I wouldn't know for sure if there's anything wrong with your code, as I haven't run your code. I am assuming you have implemented things correctly in my above comment. $\endgroup$
    – spektr
    May 1 '16 at 5:35
  • $\begingroup$ Oh, OK.:)) The point is that I am new to all this. This is not something hard, I expect, from the computer programming point of view. As a matter of fact, this is really a small program - 60 lines of code. But again, because I am newbie, it could be that there is a mistake in the code. :/ $\endgroup$
    – DDCh
    May 1 '16 at 6:50

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.