Skip to main content

how to prioritize multi-objective MILP problem in Python?

Answered
Burcu Genc
  • Gurobi-versary
  • First Question
  • First Comment

Hello, 

 i have code for a multi-objective MIP scheduling problem. These 2 are tardiness and completion time minimization.
Here I want the Tardiness objective one of my objective functions to have more effect. Or what do I need to add to my model to keep the Tardiness at a constant value?

my code:

# Veriler

machines = makine

jobs = Is

process_time = process_time

setup_time = setup_time_product_id

preparation_time = preperation_time

due_date = termin

sequence = sequence

M1 = M1

M2=M2

model = gp.Model('Makine Planlama',env=env)

if "Completion" not in orders.columns:

    # Değişkenler

    Y = model.addVars(jobs,machines , sequence, vtype=gp.GRB.BINARY, name='Y') # makina= j / iş=k

    C = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='C')

    T = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='T')

    #E = model.addVars(machines,jobs, vtype=gp.GRB.INTEGER, name='E')

    model.setObjective( gp.quicksum(T[j,k] for j in machines for k in jobs),weight=1.0,sense=gp.GRB.MINIMIZE)

    model.setObjective( gp.quicksum(C[j,k] for j in machines for k in jobs),weight=0.5,sense=gp.GRB.MINIMIZE)

    # Kısıt 1

    for k in jobs:

        for o in sequence:

            if (o==0):

                for j in machines:

                            model.addConstr(C[j,k] >= process_time[k][j]   - ( M1 * (1 - Y[k,j,o] ) ) + preparation_time[k] , name=f"constr_1_{k}_{o}_{j}")

    # Kısıt 2

    for k in jobs:

        for j in machines:

            for o in sequence:

                if (o != 0):

                    for l in jobs:

                        if k != l:

                            product_id_k=machine_last.loc[machine_last["Order Number"] ==k ,'product_id'].values[0]

                            product_id_l=machine_last.loc[machine_last["Order Number"] ==l ,'product_id'].values[0]

                            model.addConstr(C[j,k] >= C[j,l]  - (M2 * (2 - Y[l,j,(o-1)] - Y[k,j,o] )) + setup_time[product_id_k][product_id_l] + process_time[k][j], name=f"constr_2_{k}_{j}_{o}_{l}")        

    # Kısıt 3

    # Bir makinenin her bir işlem sırasına en çok bir iş atması gerektiği söylenmektedir

    for j in machines:

        for o in sequence:

            model.addConstr(gp.quicksum(Y[k,j,o] for k in jobs) <= 1, name=f"constr_3_{j}_{o}")

    # Kısıt 4

    # her bir işin bir makinenin bir sırasına atanması gerektiği söylenmektedir.

    for k in jobs:

        model.addConstr(gp.quicksum(Y[k,j,o] for o in sequence for j in machines ) == 1, name=f"constr_4_{k}")    

    # Kısıt 5

    for k in jobs:

        for j in machines:

            model.addConstr(C[j,k] - due_date[k] <= T[j,k], name=f"constr_5_{k}_{j}")

    # Kısıt 5 EARLİNESS

    """  for k in jobs:

        for j in machines:

            model.addConstr(due_date[k] - C[j,k]   <= E[j,k], name=f"constr_5_{k}_{j}")   """        

    # 0 dan büyük olma kısıtları  

    for k in jobs:

        for j in machines:

            model.addConstr(C[j,k]>=0, name=f"constr_0_{k}_{j}")

            # 0 dan büyük olma kısıtları  

    for k in jobs:

        for j in machines:

            model.addConstr(T[j,k]>=0, name=f"constr_0_{k}_{j}")

    """for k in jobs:

        for j in machines:

            model.addConstr(E[j,k]>=0, name=f"constr_0_{k}_{j}") """        

    # j değişkeni için kısıt tanımı

    for j in machines:

        # o değişkeninin her değeri için, kısıtı ekle

        for o in sequence:

            if (o!=0):

                # k ve l değişkenlerinin farklı olması koşulu ile kısıtı ekle

                model.addConstr( gp.quicksum(Y[k,j,o] - Y[l,j,o-1] for k in jobs for l in jobs if k!=l ) <= 0, name=f"constr_6_{j}_{o}_{k}" )

   

else:

   

    C_old={}

    for i in Is:

        C_old[i]=orders[orders["Order Number"]==i]["Completion"].values[0]

       

    T_old={}

    for i in Is:

        T_old[i]=orders[orders["Order Number"]==i]["Tardiness"].values[0]

       

   

    # Değişkenler

    Y = model.addVars(jobs,machines , sequence, vtype=gp.GRB.BINARY, name='Y') # makina= j / iş=k

    C_new = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='C')

    T_new = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='T')

    S_plus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='S_plus')

    S_minus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='S_minus')

    D_minus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='D_minus')

    D_plus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='D_plus')

    #E = model.addVars(machines,jobs, vtype=gp.GRB.INTEGER, name='E')

    model.setObjective( gp.quicksum(T_new[j,k] for j in machines for k in jobs),weight=1.0,sense=gp.GRB.MINIMIZE)

    model.setObjective( gp.quicksum((S_plus[k] + S_minus[k])  for k in jobs),gp.GRB.MINIMIZE)

    model.setObjective( gp.quicksum((D_plus[k] + D_minus[k])  for k in jobs),gp.GRB.MINIMIZE)

    model.setObjective( gp.quicksum(C_new[j,k] for j in machines for k in jobs),weight=0.5,sense=gp.GRB.MINIMIZE)

    # Kısıt 1

    for k in jobs:

        for o in sequence:

            if (o==0):

                for j in machines:

                            model.addConstr(C_new[j,k] >= C_min +   process_time[k][j]   - ( M1 * (1 - Y[k,j,o] ) ) + preparation_time[k] , name=f"constr_1_{k}_{o}_{j}")

    # Kısıt 2

    for k in jobs:

        for j in machines:

            for o in sequence:

                if (o != 0):

                    for l in jobs:

                        if k != l:

                            product_id_k=machine_last.loc[machine_last["Order Number"] ==k ,'product_id'].values[0]

                            product_id_l=machine_last.loc[machine_last["Order Number"] ==l ,'product_id'].values[0]

                            model.addConstr(C_new[j,k] >=    C_new[j,l]  - (M2 * (2 - Y[l,j,(o-1)] - Y[k,j,o] )) + setup_time[product_id_k][product_id_l] + process_time[k][j], name=f"constr_2_{k}_{j}_{o}_{l}")        

    # Kısıt 3

    # Bir makinenin her bir işlem sırasına en çok bir iş atması gerektiği söylenmektedir

    for j in machines:

        for o in sequence:

            model.addConstr(gp.quicksum(Y[k,j,o] for k in jobs) <= 1, name=f"constr_3_{j}_{o}")

    # Kısıt 4

    # her bir işin bir makinenin bir sırasına atanması gerektiği söylenmektedir.

    for k in jobs:

        model.addConstr(gp.quicksum(Y[k,j,o] for o in sequence for j in machines ) == 1, name=f"constr_4_{k}")    

    # Kısıt 5

    for k in jobs:

        for j in machines:

            model.addConstr(C_new[j,k] - due_date[k] <= T_new[j,k], name=f"constr_5_{k}_{j}")

    # Kısıt 5 EARLİNESS

    """  for k in jobs:

        for j in machines:

            model.addConstr(due_date[k] - C[j,k]   <= E[j,k], name=f"constr_5_{k}_{j}")   """        

    # 0 dan büyük olma kısıtları  

    for k in jobs:

        for j in machines:

            model.addConstr(C_new[j,k]>=0 , name=f"constr_0_{k}_{j}")

            # 0 dan büyük olma kısıtları  

    for k in jobs:

        for j in machines:

            model.addConstr(T_new[j,k]>=0, name=f"constr_0_{k}_{j}")

    """for k in jobs:

        for j in machines:

            model.addConstr(E[j,k]>=0, name=f"constr_0_{k}_{j}") """        

    # j değişkeni için kısıt tanımı

    for j in machines:

        # o değişkeninin her değeri için, kısıtı ekle

        for o in sequence:

            if (o!=0):

                # k ve l değişkenlerinin farklı olması koşulu ile kısıtı ekle

                model.addConstr( gp.quicksum(Y[k,j,o] - Y[l,j,o-1] for k in jobs for l in jobs if k!=l ) <= 0, name=f"constr_6_{j}_{o}_{k}" )

               

    for k in jobs:

        for j in machines:

            model.addConstr(C_new[j,k]==C_old[k]+ S_plus[k] - S_minus[k]  , name=f"constr_0_{k}_{j}")    

           

                           

    for k in jobs:

        for j in machines:

            model.addConstr(T_new[j,k]==T_old[k]+ D_plus[k] - D_minus[k] , name=f"constr_0_{k}_{j}")      

    for k in jobs:

        model.addConstr(S_plus[k]>=0, name=f"constr_0_{k}")

       

    for k in jobs:

        model.addConstr(S_minus[k]>=0, name=f"constr_0_{k}")

    for k in jobs:

        model.addConstr(D_plus[k]>=0, name=f"constr_0_{k}")

    for k in jobs:

        model.addConstr(D_minus[k]>=0, name=f"constr_0_{k}")

   

Related to

0

Comments

5 comments

Date Votes
  • Marika Karbstein
    • Gurobi Staff Gurobi Staff

    Hi Burcu,

    Let me point out two issues in your code:

    Please note that Model.setObjective() always replaces the existing objective. For example, if you have

    m.setObjective(x + y)
    m.setObjective(2*z)
    the objective is \(2*z\) at the end not \(x+y+2*z\).
     
    If you want to define multiple objectives, you need to use Model.setObjectiveN(). Here, you can define index=0, priority=2 for your tardiness objective and index=1, priority=1 for the other objective. Then the tardiness objective is added as a constraint when solving the second objective. See also the documentation on Multiple Objectives and Specifying Multiple Objectives for more details. 
    Please note, also here the objective is replaced if you call setObjectiveN a second time for the same index.
     
    Cheers,
    Marika
    0
  • Burcu Genc
    Edited
    • Gurobi-versary
    • First Question
    • First Comment

    Hello Marika,

    Thanks. I used it. It worked but the first tardiness value is 8220 and the second tardiness (the code is worked 2nd time) value is 8853 on this code. How can i get the tardiness value which is less than or equal to 8220? where did i go wrong?

     


    # Veriler

    machines = makine

    jobs = Is

    process_time = process_time

    setup_time = setup_time_product_id

    preparation_time = preperation_time

    due_date = termin

    sequence = sequence

    M1 = M1

    M2=M2

    model = gp.Model('Makine Planlama',env=env)

    if "Completion" not in orders.columns:

        # Değişkenler

        Y = model.addVars(jobs,machines , sequence, vtype=gp.GRB.BINARY, name='Y') # makina= j / iş=k

        C = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='C')

        T = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='T')

        #E = model.addVars(machines,jobs, vtype=gp.GRB.INTEGER, name='E')

        model.setObjective( gp.quicksum(T[j,k] for j in machines for k in jobs),gp.GRB.MINIMIZE)

        #model.setObjective( gp.quicksum(C[j,k] for j in machines for k in jobs),gp.GRB.MINIMIZE)

        # Kısıt 1

        for k in jobs:

            for o in sequence:

                if (o==0):

                    for j in machines:

                                model.addConstr(C[j,k] >= process_time[k][j]   - ( M1 * (1 - Y[k,j,o] ) ) + preparation_time[k] , name=f"constr_1_{k}_{o}_{j}")

        # Kısıt 2

        for k in jobs:

            for j in machines:

                for o in sequence:

                    if (o != 0):

                        for l in jobs:

                            if k != l:

                                product_id_k=machine_last.loc[machine_last["Order Number"] ==k ,'product_id'].values[0]

                                product_id_l=machine_last.loc[machine_last["Order Number"] ==l ,'product_id'].values[0]

                                model.addConstr(C[j,k] >= C[j,l]  - (M2 * (2 - Y[l,j,(o-1)] - Y[k,j,o] )) + setup_time[product_id_k][product_id_l] + process_time[k][j], name=f"constr_2_{k}_{j}_{o}_{l}")        

        # Kısıt 3

        # Bir makinenin her bir işlem sırasına en çok bir iş atması gerektiği söylenmektedir

        for j in machines:

            for o in sequence:

                model.addConstr(gp.quicksum(Y[k,j,o] for k in jobs) <= 1, name=f"constr_3_{j}_{o}")

        # Kısıt 4

        # her bir işin bir makinenin bir sırasına atanması gerektiği söylenmektedir.

        for k in jobs:

            model.addConstr(gp.quicksum(Y[k,j,o] for o in sequence for j in machines ) == 1, name=f"constr_4_{k}")    

        # Kısıt 5

        for k in jobs:

            for j in machines:

                model.addConstr(C[j,k] - due_date[k] <= T[j,k], name=f"constr_5_{k}_{j}")

        # Kısıt 5 EARLİNESS

        """  for k in jobs:

            for j in machines:

                model.addConstr(due_date[k] - C[j,k]   <= E[j,k], name=f"constr_5_{k}_{j}")   """        

        # 0 dan büyük olma kısıtları  

        for k in jobs:

            for j in machines:

                model.addConstr(C[j,k]>=0, name=f"constr_0_{k}_{j}")

                # 0 dan büyük olma kısıtları  

        for k in jobs:

            for j in machines:

                model.addConstr(T[j,k]>=0, name=f"constr_0_{k}_{j}")

        """for k in jobs:

            for j in machines:

                model.addConstr(E[j,k]>=0, name=f"constr_0_{k}_{j}") """        

        # j değişkeni için kısıt tanımı

        for j in machines:

            # o değişkeninin her değeri için, kısıtı ekle

            for o in sequence:

                if (o!=0):

                    # k ve l değişkenlerinin farklı olması koşulu ile kısıtı ekle

                    model.addConstr( gp.quicksum(Y[k,j,o] - Y[l,j,o-1] for k in jobs for l in jobs if k!=l ) <= 0, name=f"constr_6_{j}_{o}_{k}" )

       

    else:

       

        C_old={}

        for i in Is:

            C_old[i]=orders[orders["Order Number"]==i]["Completion"].values[0]

           

        T_old={}

        for i in Is:

            T_old[i]=orders[orders["Order Number"]==i]["Tardiness"].values[0]

           

       

        # Değişkenler

        Y = model.addVars(jobs,machines , sequence, vtype=gp.GRB.BINARY, name='Y') # makina= j / iş=k

        C_new = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='C')

        T_new = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='T')

        S_plus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='S_plus')

        S_minus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='S_minus')

        D_minus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='D_minus')

        D_plus= model.addVars(jobs, vtype=gp.GRB.INTEGER, name='D_plus')

        #E = model.addVars(machines,jobs, vtype=gp.GRB.INTEGER, name='E')

        model.setObjectiveN( gp.quicksum(T_new[j,k] for j in machines for k in jobs),gp.GRB.MINIMIZE)

        model.setObjectiveN( gp.quicksum((S_plus[k] + S_minus[k])  for k in jobs),index=1, priority=3)

        model.setObjectiveN( gp.quicksum((D_plus[k] + D_minus[k])  for k in jobs),index=1, priority=4)

        model.setObjectiveN( gp.quicksum(C_new[j,k] for j in machines for k in jobs),index=1, priority=2)

       

        # Kısıt 1

        for k in jobs:

            for o in sequence:

                if (o==0):

                    for j in machines:

                                model.addConstr(C_new[j,k] >= C_min +   process_time[k][j]   - ( M1 * (1 - Y[k,j,o] ) ) + preparation_time[k] , name=f"constr_1_{k}_{o}_{j}")

        # Kısıt 2

        for k in jobs:

            for j in machines:

                for o in sequence:

                    if (o != 0):

                        for l in jobs:

                            if k != l:

                                product_id_k=machine_last.loc[machine_last["Order Number"] ==k ,'product_id'].values[0]

                                product_id_l=machine_last.loc[machine_last["Order Number"] ==l ,'product_id'].values[0]

                                model.addConstr(C_new[j,k] >=    C_new[j,l]  - (M2 * (2 - Y[l,j,(o-1)] - Y[k,j,o] )) + setup_time[product_id_k][product_id_l] + process_time[k][j], name=f"constr_2_{k}_{j}_{o}_{l}")        

        # Kısıt 3

        # Bir makinenin her bir işlem sırasına en çok bir iş atması gerektiği söylenmektedir

        for j in machines:

            for o in sequence:

                model.addConstr(gp.quicksum(Y[k,j,o] for k in jobs) <= 1, name=f"constr_3_{j}_{o}")

        # Kısıt 4

        # her bir işin bir makinenin bir sırasına atanması gerektiği söylenmektedir.

        for k in jobs:

            model.addConstr(gp.quicksum(Y[k,j,o] for o in sequence for j in machines ) == 1, name=f"constr_4_{k}")    

        # Kısıt 5

        for k in jobs:

            for j in machines:

                model.addConstr(C_new[j,k] - due_date[k] <= T_new[j,k], name=f"constr_5_{k}_{j}")

        # Kısıt 5 EARLİNESS

        """  for k in jobs:

            for j in machines:

                model.addConstr(due_date[k] - C[j,k]   <= E[j,k], name=f"constr_5_{k}_{j}")   """        

        # 0 dan büyük olma kısıtları  

        for k in jobs:

            for j in machines:

                model.addConstr(C_new[j,k]>=0 , name=f"constr_0_{k}_{j}")

                # 0 dan büyük olma kısıtları  

        for k in jobs:

            for j in machines:

                model.addConstr(T_new[j,k]>=0, name=f"constr_0_{k}_{j}")

        """for k in jobs:

            for j in machines:

                model.addConstr(E[j,k]>=0, name=f"constr_0_{k}_{j}") """        

        # j değişkeni için kısıt tanımı

        for j in machines:

            # o değişkeninin her değeri için, kısıtı ekle

            for o in sequence:

                if (o!=0):

                    # k ve l değişkenlerinin farklı olması koşulu ile kısıtı ekle

                    model.addConstr( gp.quicksum(Y[k,j,o] - Y[l,j,o-1] for k in jobs for l in jobs if k!=l ) <= 0, name=f"constr_6_{j}_{o}_{k}" )

                   

        for k in jobs:

            for j in machines:

                model.addConstr(C_new[j,k]==C_old[k]+ S_plus[k] - S_minus[k]  , name=f"constr_0_{k}_{j}")    

               

                               

        for k in jobs:

            for j in machines:

                model.addConstr(T_new[j,k]==T_old[k]+ D_plus[k] - D_minus[k] , name=f"constr_0_{k}_{j}")      

        for k in jobs:

            model.addConstr(S_plus[k]>=0, name=f"constr_0_{k}")

           

        for k in jobs:

            model.addConstr(S_minus[k]>=0, name=f"constr_0_{k}")

        for k in jobs:

            model.addConstr(D_plus[k]>=0, name=f"constr_0_{k}")

        for k in jobs:

            model.addConstr(D_minus[k]>=0, name=f"constr_0_{k}")

       


    0
  • Marika Karbstein
    • Gurobi Staff Gurobi Staff

    Your code is not executable and I do not fully understand your problem and setup.

    Could you please provide a minimal reproducible example? See Tutorial: Preparing a Minimal Reproducible Example – Gurobi Help Center

     

    0
  • Burcu Genc
    Edited
    • Gurobi-versary
    • First Question
    • First Comment

    Hello Marika,

    my code consists of 2 stages. The first part is taken into account when I run it for the first time, and the second part is taken into account in my 2nd and subsequent runs.

    When I run the code for the first time, the following objective function works; This objective function is based on Tardiness as M1 is a large number. There is no problem with this.

    if "Completion" not in orders.columns:

        # Değişkenler

        Y = model.addVars(jobs,machines , sequence, vtype=gp.GRB.BINARY, name='Y') # makina= j / iş=k

        C = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='C')

        T = model.addVars(machines,jobs, vtype=gp.GRB.CONTINUOUS, name='T')

        #E = model.addVars(machines,jobs, vtype=gp.GRB.INTEGER, name='E')

        # İlk aşama: T değerlerinin minimumunu bulma

        total_obj1 = gp.quicksum(T[j, k] for j in machines for k in jobs)

        total_obj2 = gp.quicksum(C[j, k] for j in machines for k in jobs)

        weight_T = M1  # T değerlerine verilecek ağırlık

        weight_C = 1  # C değerlerine verilecek ağırlık

        total_obj = weight_T * total_obj1 + weight_C * total_obj2

        model.setObjective(total_obj, gp.GRB.MINIMIZE)
    The main problem is in part 2 of the code, when I run the code for the first time, tardiness = 8220 minutes. This is the optimal solution. when I run it for the second time, tardiness=14000 comes around. Normally, I used the Blended Objectives method. I summed up them but now, I need to use Hierarchical Objectives.
    In other words, it should take the Tardiness from the first run as a constraint in the second run. When I set priority, it takes into account the objective that is written at the bottom, respectively. How do I fix this error? Could you write me a true code?
     
    model.setObjectiveN( gp.quicksum(T_new[j,k] for j in machines for k in jobs),gp.GRB.MINIMIZE)
        model.setObjectiveN( gp.quicksum((S_plus[k] + S_minus[k])  for k in jobs),index=1, priority=3)
        model.setObjectiveN( gp.quicksum((D_plus[k] + D_minus[k])  for k in jobs),index=1, priority=4)
        model.setObjectiveN( gp.quicksum(C_new[j,k] for j in machines for k in jobs),index=1, priority=2)
     
     

     

    0
  • Marika Karbstein
    • Gurobi Staff Gurobi Staff
    Edited

    Hi Burcu,

    Your multi-objective definition does not look right. You need to use a unique index for each objective. The objective with the highest priority is solved first and then the result is added as a constraint to the next level. So if minimizing the sum of T_new is most important you might want to have something like

    model.setObjectiveN( gp.quicksum(T_new[j,k] for j in machines for k in jobs), index=0, prority=5)
    model.setObjectiveN( gp.quicksum((S_plus[k] + S_minus[k])  for k in jobs),index=1, priority=3)
    model.setObjectiveN( gp.quicksum((D_plus[k] + D_minus[k])  for k in jobs),index=2, priority=4)
    model.setObjectiveN( gp.quicksum(C_new[j,k] for j in machines for k in jobs),index=3, priority=2)

    Note that the objective sense is no input argument for Model.setObjectiveN().
    The default is to minimize, so nothing needs to be done here. If you want to change the objective sense, you need to change the model attribute ModelSense.

    I also recommend writing the model as an lp-file using model.write("Test.lp") and then check if this looks like you intended.

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post