Infeasible solution on Gurobi/Python Model (Scheduling Model Mixed Integer Programming)

Hello Everyone,

Here is my mathematical model and constraints;

(indice i can be ignored)

Objective function aims to minimize tardiness of the jobs.Constraint (I) states that if a job is placed in rank 1 on any machine, the completion time must be greater than and equal to the processing time and preparation start time. According to Constraint (II) If a job is placed in a queue 2 or higher, the completion time must be greater than the sum of the previous job’s completion processing time and setup time. In Constraint (III), a maximum of one job will be assigned to each processing queue of a machine is stated. Constraint (IV) states that each job is assigned to a row of a machine. In Constraint (V) If a job’s completion time is greater than its deadline, it creates tardiness is stated. Constraint (VI) allows jobs to be sequentially
ordered. Then, lastly, it can be seen that the nonnegativity constraints.

Here is my Python code;

# Veriler (makine,Is,termin and preperation_time are dictionaries.)
machines = makine
jobs = Is
process_time = process_time
setup_time = setup_time
preparation_time = preperation_time
due_date = termin
sequence = sequence
M = 300000

model = gp.Model('Makine Planlama',env=env)
# 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.INTEGER, name='C')
T = model.addVars(machines,jobs, vtype=gp.GRB.INTEGER, name='T')

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

# Cons 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]   - ( M * (1 - Y[k,j,o] ) ) + preparation_time[k] )
                    
# Cons 2
for k in jobs:
    for j in machines:
        for o in sequence:
            if (o != 0):
                for l in jobs:
                    if k != l:
                        model.addConstr(C[j,k] >= C[j,l]  - (M * (2 - Y[k,j,(o-1)] - Y[l,j,o] )) + setup_time[k][l] + process_time[k][j])        
                        
# Cons 3
for j in machines:
    for o in sequence:
        model.addConstr(gp.quicksum(Y[k,j,o] for k in jobs) <= 1)
        
# Cons 4
for k in jobs:
    model.addConstr(gp.quicksum(Y[k,j,o] for o in sequence for j in machines ) == 1)    
    
    
# Cons 5
for k in jobs:
    for j in machines:
        model.addConstr(C[j,k] - due_date[k] <= T[j,k]) 

# Cons 6
   for j in machines:
    for o in sequence:
         for k in jobs:
            for l in jobs:
                if (k != l) & (o!=0):
                    model.addConstr(@quicksum(
                        Y[k,j,o]) - (@quicksumY[l,j,o-1]) <= 0)

# Nonnegativity
for k in jobs:
    for j in machines:
        model.addConstr(C[j,k]>=0)

Could you please give me a reason for infeasibility and help me :)

Jonasz Staszek

Community Moderator

May 03, 2023 06:57

Hi Burcu,

this article should be of help.

I would also recommend that you do add some meaningful names to your constraints. This way, it will be easier to analyze the IIS.

You should also try generating the IIS for the smallest instance for which the infeasibility occurs.

Hope this helps.

Best regards
Jonasz

Burcu Genc

May 03, 2023 08:15

Hello Jonasz, Thank you for your opinion.

But, I did not understand exactly for adding some meaningful names to your constraints.And also, trying to generate the IIS for the smallest instance for which the infeasibility occurs.

Could you please give an example?

Kind Regards

Burcu

May 03, 2023 08:42

adding some meaningful names to your constraints.

the documentation of the addConstrs() method mentions the 'name' parameter, which you can use to give your constraints a name. The same holds for the addConstr() method.

Adding a name important if you wish to browse your model in the text form. Otherwise your constraints get generic names like R112 and it is very difficult to identify them.

An example from your code would be (assuming you use Python 3.7 or newer):

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}")

This way each of your constraints is clearly identifiable. This will be important later on.

And also, trying to generate the IIS for the smallest instance for which the infeasibility occurs.

I guess you tested your model on several datasets / instances.

For some of them, the model implemented by your code could be feasible, for others not.

After ensuring that all your constraints have a name, I would take the smallest dataset which causes infeasibility.

Then I would compute the IIS by running

# ... model generation above
model.optimize()
model.computeIIS()
model.write("IIS.ilp")

and study the resulting IIS.ilp file. This should give you an idea for the reasons of your infeasibility.

I hope this makes things clearer. If you need further clarification, do not hesitate to contact us.

Infeasible solution on Gurobi/Python Model (Scheduling Model Mixed Integer Programming)

Comments

Didn't find what you were looking for?