メインコンテンツへスキップ

Car Sequencing Problem Implementation Using Gurobi

ユーザーの入力を待っています。
Carlos Ferreira
  • Gurobi-versary
  • First Comment
  • First Question

Dear all from the community, I hope you are well and get prepared for the Holiday Season!

I am trying to implement the following model using Gurobi in Python:

My code is the following (I am sorry for the comments in Portuguese):

#Car Sequencing Problem

####Inicialização do Problema####

#Importa as bibliotecas necessárias
from gurobipy import *
import math
import numpy as np

def read_integers(filename):
with open("instance_with_results/0_00.in") as f:
return [int(elem) for elem in f.read().split()]

#O formato dos ficheiros de dados é o seguinte::
#-> 1ª linha: número de carros; número de opções; número de classes.
#-> 2ª linha: para cada opção, o número máximo de carros com essa opção num bloco.
#-> 3ª linha: para cada opção, o tamanho do bloco a que se refere o número máximo.
#-> Depois para cada classe: nº de índice; nº de carros nesta classe; para cada opção, quer esta classe o exija ou não (1 ou 0).


# Lê Instâncias
file_it = iter(read_integers("instance_with_results/0_00.in")) #Cria um objecto que pode ser iterado um elemento de cada vez. 
NC = next(file_it) #Número total de carros.
OPT = next(file_it) #Número total de opcionais.
CL = next(file_it) #Número total de classes == modelos (ou variantes).
r = [next(file_it) for k in range(OPT)] #O número máximo de carros que podem ter a opção "k" numa sequência consecutiva de carros "s[k]".
s = [next(file_it) for k in range(OPT)] #A duração de uma sequência consecutiva de carros, alguns dos quais requerem a opção "k"
n = [] #Inicia uma lista que conterá o número total de carros na classe "i"
o = [] #Inicia uma lista que conterá um parâmetro booleano que mostra se os carros da classe "i" requerem a opção "k"

for i in range(CL): #Detro do número de classes, inicia a leitura das restantes linhas.
next(file_it) #Lê a 1ª coluna de cada linha = Index da class = [0,...,cl]
n.append(next(file_it)) #Lê a 2ª coluna de cada linha = Número de carros em cada classe e adicional da lista "n[]".
o.append([next(file_it) == 1 for k in range(OPT)]) #Lê as próximas colunas e cria um vetor linha contendo para cada classe "i" os opcionais "k" requeridos.

#-----------------------------------------------Variáveis de decisão-----------------------------------------------------------------------------

md = Model('SEQ')


y = {} #y[k,j] = 1 se há violações da capacidade para o opcional "k" em cada posição "j", 0 caso contrário == Paper [9].
for k in range(OPT):
for j in range(NC-s[k]+1):
y[k,j] = md.addVar(vtype=GRB.BINARY, name="y[%d,%d]" % (k,j))

c = {} #c[i,j] = 1 se carro da classe "i" está na posição "j" da linha, 0 caso contrário == Paper [9].
for i in range(CL):
for j in range(NC):
c[i,j] = md.addVar(vtype=GRB.BINARY, name="c[%d,%d]" % (i,j))

#---------------------------------------------------------------Modelo-----------------------------------------------------------------------------

####---------------------Função Objetivo-----------------------

#Soma o número de violações para todas as opções em todas as janelas == Equação (1) == Paper [9].
obj = quicksum(
y[k,j]
for k in range(OPT)
for j in range(NC-s[k]+1)
)

####---------------------Constraints-----------------------

#Esse constraint assegura que termos somente um carro em cada posição p == Equação (2) == Paper [9].
md.addConstrs(
quicksum(c[i,j] for i in range(CL)) == 1
for j in range(NC)
)

#Esse constraint assegura que todos os carros de uma classe estão em uma posição, ou seja, que a demanda é satisfeita == Equação (3) == Paper [9].
md.addConstrs(
quicksum(c[i,j] for j in range(NC)) == n[i]
for i in range(CL)
)

#Esse constraint formaliza a restrições do tipo r[k]/s[k] ligadas às várias opções, permitindo que sejam violadas a um custo se não for possível
#achar uma solução feasible == Equação (4) == Paper [9].

md.addConstrs(
quicksum(o[i][k]*c[i,l] for i in range(CL) for l in range(j,j+s[k]-1)) <= r[k] + (s[k]-r[k])*y[k,j]
for k in range(OPT)
for j in range((NC-s[k]+1))
)

#Minimiza o número de violações para todas as opções em todas as janelas
md.setObjective(obj, GRB.MINIMIZE)

# Limita o tempo de processamento em 600 segundos == Paper [6], Section 5.
md.setParam(GRB.Param.TimeLimit, 600.0)

#Roda o modelo de optimização
md.optimize()

#Define os códigos de status da solução
status_code = {1:'LOADED', 2:'OPTIMAL', 3:'INFEASIBLE', 4:'INF_OR_UNBD', 5:'UNBOUNDED'}
status = md.status

# Escreve a solução em um ficheiro
with open("solution_0_00.txt", 'w') as f:
f.write('O Status da otimização é: {}\n'.format(status_code[status]))
if status == 2:
f.write("O número total de violações é:{0:.2f}\n" .format(md.objVal))
f.write("A melhor sequência de carros é:\n")
for j in range(NC):
for i in range(CL): 
if c[i,j].x == 1:
f.write("%d " % i)
break
f.write("\n")

The code runs with no error, but, however, it does not provide the correct solution for the instance I am using for the test. I've been looking for errors, but I can't find any. I have wasted many hours on this to no avail. Could someone please check the code and see if I'm missing something? This would be a really great Christmas gift!!!

The instance I am using as a test is the following (0_00):

10 5 6
1 2 1 2 1
2 3 3 5 5
0 1 1 0 1 1 0 
1 1 0 0 0 1 0 
2 2 0 1 0 0 1 
3 2 0 1 0 1 0 
4 2 1 0 1 0 0 
5 2 1 1 0 0 0

The correct sequence for this instance is:

0 1 5 2 4 3 3 4 2 5

I really appreciate your effort to help me and thank you in advance!

Finally, my best wishes of peace and health for 2022 for everyone!

0

コメント

4件のコメント

日付 投票
  • 正式なコメント
    Simranjit Kaur
    • Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff
    編集済み

    Hi Carlos,

    Did you try to write your model out to a file via

    md.write("myLP.lp")

    and analyzing it? This should help here.

    Is it possible that your model has more that 1 optimal solution?

    Best regards,
    Jaromił

    0
  • Carlos Ferreira
    • Gurobi-versary
    • First Comment
    • First Question

    Dear Jaromił Najman, thanks for your suggestion! I tried to do this but, definitively, it did not help me... The output is below:

    \ Model car_sequencing
    \ LP format - for model browsing. Use MPS format to capture full model detail.
    Minimize
    0 r[0] + 0 r[1] + 0 r[2] + 0 r[3] + 0 r[4] + 0 s[0] + 0 s[1] + 0 s[2]
    + 0 s[3] + 0 s[4] + 0 n[0] + 0 n[1] + 0 n[2] + 0 n[3] + 0 n[4] + 0 n[5]
    + 0 o[0,0] + 0 o[0,1] + 0 o[0,2] + 0 o[0,3] + 0 o[0,4] + 0 o[1,0]
    + 0 o[1,1] + 0 o[1,2] + 0 o[1,3] + 0 o[1,4] + 0 o[2,0] + 0 o[2,1]
    + 0 o[2,2] + 0 o[2,3] + 0 o[2,4] + 0 o[3,0] + 0 o[3,1] + 0 o[3,2]
    + 0 o[3,3] + 0 o[3,4] + 0 o[4,0] + 0 o[4,1] + 0 o[4,2] + 0 o[4,3]
    + 0 o[4,4] + 0 o[5,0] + 0 o[5,1] + 0 o[5,2] + 0 o[5,3] + 0 o[5,4]
    + y[0,0] + y[0,1] + y[0,2] + y[0,3] + y[0,4] + y[0,5] + y[0,6] + y[0,7]
    + y[0,8] + y[1,0] + y[1,1] + y[1,2] + y[1,3] + y[1,4] + y[1,5] + y[1,6]
    + y[1,7] + y[2,0] + y[2,1] + y[2,2] + y[2,3] + y[2,4] + y[2,5] + y[2,6]
    + y[2,7] + y[3,0] + y[3,1] + y[3,2] + y[3,3] + y[3,4] + y[3,5] + y[4,0]
    + y[4,1] + y[4,2] + y[4,3] + y[4,4] + y[4,5]
    Subject To
    R0: c[0,0] + c[1,0] + c[2,0] + c[3,0] + c[4,0] + c[5,0] = 1
    R1: c[0,1] + c[1,1] + c[2,1] + c[3,1] + c[4,1] + c[5,1] = 1
    R2: c[0,2] + c[1,2] + c[2,2] + c[3,2] + c[4,2] + c[5,2] = 1
    R3: c[0,3] + c[1,3] + c[2,3] + c[3,3] + c[4,3] + c[5,3] = 1
    R4: c[0,4] + c[1,4] + c[2,4] + c[3,4] + c[4,4] + c[5,4] = 1
    R5: c[0,5] + c[1,5] + c[2,5] + c[3,5] + c[4,5] + c[5,5] = 1
    R6: c[0,6] + c[1,6] + c[2,6] + c[3,6] + c[4,6] + c[5,6] = 1
    R7: c[0,7] + c[1,7] + c[2,7] + c[3,7] + c[4,7] + c[5,7] = 1
    R8: c[0,8] + c[1,8] + c[2,8] + c[3,8] + c[4,8] + c[5,8] = 1
    R9: c[0,9] + c[1,9] + c[2,9] + c[3,9] + c[4,9] + c[5,9] = 1
    R10: c[0,0] + c[0,1] + c[0,2] + c[0,3] + c[0,4] + c[0,5] + c[0,6] + c[0,7]
    + c[0,8] + c[0,9] = 1
    R11: c[1,0] + c[1,1] + c[1,2] + c[1,3] + c[1,4] + c[1,5] + c[1,6] + c[1,7]
    + c[1,8] + c[1,9] = 1
    R12: c[2,0] + c[2,1] + c[2,2] + c[2,3] + c[2,4] + c[2,5] + c[2,6] + c[2,7]
    + c[2,8] + c[2,9] = 2
    R13: c[3,0] + c[3,1] + c[3,2] + c[3,3] + c[3,4] + c[3,5] + c[3,6] + c[3,7]
    + c[3,8] + c[3,9] = 2
    R14: c[4,0] + c[4,1] + c[4,2] + c[4,3] + c[4,4] + c[4,5] + c[4,6] + c[4,7]
    + c[4,8] + c[4,9] = 2
    R15: c[5,0] + c[5,1] + c[5,2] + c[5,3] + c[5,4] + c[5,5] + c[5,6] + c[5,7]
    + c[5,8] + c[5,9] = 2
    R16: - y[0,0] + c[0,0] + c[4,0] + c[5,0] <= 1
    R17: - y[0,1] + c[0,1] + c[4,1] + c[5,1] <= 1
    R18: - y[0,2] + c[0,2] + c[4,2] + c[5,2] <= 1
    R19: - y[0,3] + c[0,3] + c[4,3] + c[5,3] <= 1
    R20: - y[0,4] + c[0,4] + c[4,4] + c[5,4] <= 1
    R21: - y[0,5] + c[0,5] + c[4,5] + c[5,5] <= 1
    R22: - y[0,6] + c[0,6] + c[4,6] + c[5,6] <= 1
    R23: - y[0,7] + c[0,7] + c[4,7] + c[5,7] <= 1
    R24: - y[0,8] + c[0,8] + c[4,8] + c[5,8] <= 1
    R25: - y[1,0] + c[2,0] + c[2,1] + c[3,0] + c[3,1] + c[5,0] + c[5,1] <= 2
    R26: - y[1,1] + c[2,1] + c[2,2] + c[3,1] + c[3,2] + c[5,1] + c[5,2] <= 2
    R27: - y[1,2] + c[2,2] + c[2,3] + c[3,2] + c[3,3] + c[5,2] + c[5,3] <= 2
    R28: - y[1,3] + c[2,3] + c[2,4] + c[3,3] + c[3,4] + c[5,3] + c[5,4] <= 2
    R29: - y[1,4] + c[2,4] + c[2,5] + c[3,4] + c[3,5] + c[5,4] + c[5,5] <= 2
    R30: - y[1,5] + c[2,5] + c[2,6] + c[3,5] + c[3,6] + c[5,5] + c[5,6] <= 2
    R31: - y[1,6] + c[2,6] + c[2,7] + c[3,6] + c[3,7] + c[5,6] + c[5,7] <= 2
    R32: - y[1,7] + c[2,7] + c[2,8] + c[3,7] + c[3,8] + c[5,7] + c[5,8] <= 2
    R33: - 2 y[2,0] + c[0,0] + c[0,1] + c[4,0] + c[4,1] <= 1
    R34: - 2 y[2,1] + c[0,1] + c[0,2] + c[4,1] + c[4,2] <= 1
    R35: - 2 y[2,2] + c[0,2] + c[0,3] + c[4,2] + c[4,3] <= 1
    R36: - 2 y[2,3] + c[0,3] + c[0,4] + c[4,3] + c[4,4] <= 1
    R37: - 2 y[2,4] + c[0,4] + c[0,5] + c[4,4] + c[4,5] <= 1
    R38: - 2 y[2,5] + c[0,5] + c[0,6] + c[4,5] + c[4,6] <= 1
    R39: - 2 y[2,6] + c[0,6] + c[0,7] + c[4,6] + c[4,7] <= 1
    R40: - 2 y[2,7] + c[0,7] + c[0,8] + c[4,7] + c[4,8] <= 1
    R41: - 3 y[3,0] + c[0,0] + c[0,1] + c[0,2] + c[0,3] + c[1,0] + c[1,1]
    + c[1,2] + c[1,3] + c[3,0] + c[3,1] + c[3,2] + c[3,3] <= 2
    R42: - 3 y[3,1] + c[0,1] + c[0,2] + c[0,3] + c[0,4] + c[1,1] + c[1,2]
    + c[1,3] + c[1,4] + c[3,1] + c[3,2] + c[3,3] + c[3,4] <= 2
    R43: - 3 y[3,2] + c[0,2] + c[0,3] + c[0,4] + c[0,5] + c[1,2] + c[1,3]
    + c[1,4] + c[1,5] + c[3,2] + c[3,3] + c[3,4] + c[3,5] <= 2
    R44: - 3 y[3,3] + c[0,3] + c[0,4] + c[0,5] + c[0,6] + c[1,3] + c[1,4]
    + c[1,5] + c[1,6] + c[3,3] + c[3,4] + c[3,5] + c[3,6] <= 2
    R45: - 3 y[3,4] + c[0,4] + c[0,5] + c[0,6] + c[0,7] + c[1,4] + c[1,5]
    + c[1,6] + c[1,7] + c[3,4] + c[3,5] + c[3,6] + c[3,7] <= 2
    R46: - 3 y[3,5] + c[0,5] + c[0,6] + c[0,7] + c[0,8] + c[1,5] + c[1,6]
    + c[1,7] + c[1,8] + c[3,5] + c[3,6] + c[3,7] + c[3,8] <= 2
    R47: - 4 y[4,0] + c[2,0] + c[2,1] + c[2,2] + c[2,3] <= 1
    R48: - 4 y[4,1] + c[2,1] + c[2,2] + c[2,3] + c[2,4] <= 1
    R49: - 4 y[4,2] + c[2,2] + c[2,3] + c[2,4] + c[2,5] <= 1
    R50: - 4 y[4,3] + c[2,3] + c[2,4] + c[2,5] + c[2,6] <= 1
    R51: - 4 y[4,4] + c[2,4] + c[2,5] + c[2,6] + c[2,7] <= 1
    R52: - 4 y[4,5] + c[2,5] + c[2,6] + c[2,7] + c[2,8] <= 1
    Bounds
    Binaries
    y[0,0] y[0,1] y[0,2] y[0,3] y[0,4] y[0,5] y[0,6] y[0,7] y[0,8] y[1,0]
    y[1,1] y[1,2] y[1,3] y[1,4] y[1,5] y[1,6] y[1,7] y[2,0] y[2,1] y[2,2]
    y[2,3] y[2,4] y[2,5] y[2,6] y[2,7] y[3,0] y[3,1] y[3,2] y[3,3] y[3,4]
    y[3,5] y[4,0] y[4,1] y[4,2] y[4,3] y[4,4] y[4,5] c[0,0] c[0,1] c[0,2]
    c[0,3] c[0,4] c[0,5] c[0,6] c[0,7] c[0,8] c[0,9] c[1,0] c[1,1] c[1,2]
    c[1,3] c[1,4] c[1,5] c[1,6] c[1,7] c[1,8] c[1,9] c[2,0] c[2,1] c[2,2]
    c[2,3] c[2,4] c[2,5] c[2,6] c[2,7] c[2,8] c[2,9] c[3,0] c[3,1] c[3,2]
    c[3,3] c[3,4] c[3,5] c[3,6] c[3,7] c[3,8] c[3,9] c[4,0] c[4,1] c[4,2]
    c[4,3] c[4,4] c[4,5] c[4,6] c[4,7] c[4,8] c[4,9] c[5,0] c[5,1] c[5,2]
    c[5,3] c[5,4] c[5,5] c[5,6] c[5,7] c[5,8] c[5,9]
    Generals
    r[0] r[1] r[2] r[3] r[4] s[0] s[1] s[2] s[3] s[4] n[0] n[1] n[2] n[3] n[4]
    n[5] o[0,0] o[0,1] o[0,2] o[0,3] o[0,4] o[1,0] o[1,1] o[1,2] o[1,3] o[1,4]
    o[2,0] o[2,1] o[2,2] o[2,3] o[2,4] o[3,0] o[3,1] o[3,2] o[3,3] o[3,4]
    o[4,0] o[4,1] o[4,2] o[4,3] o[4,4] o[5,0] o[5,1] o[5,2] o[5,3] o[5,4]
    End

    Regarding the solutions, yes, this specific instance has six known solutions as follows. However, the solution I am retrieving (4 2 5 5 0 1 4 2 3 3 ) is not one of them.

    0 1 5 2 4 3 3 4 2 5
    0 2 5 1 4 3 2 4 3 5
    0 2 5 1 5 3 4 2 3 4
    4 3 2 4 3 5 1 5 2 0
    5 2 4 3 3 4 2 5 1 0
    5 3 4 2 3 4 1 5 2 0

    I am trying to learn optimization using Gurobi Python, and it has not been easy, mainly because I am not a specialist.

    Thanks again for your support!

    0
  • Jaromił Najman
    • Gurobi Staff Gurobi Staff

    Hi Carlos,

    You could try fixing the variable values to your solution, by setting their lower and upper bound to either 0 or 1 and check whether your solution is feasible. If it is not, you can then determine why it is infeasible as described in How do I determine why my model is infeasible? If your solution is feasible, then you have to check the objective value and try to understand why it is worse than what the other solutions provide.

    Best regards,
    Jaromił

    0

投稿コメントは受け付けていません。

お探しのものを見つけられませんでしたか？

新規投稿