Solution not found or model is infeasible ( Gurobi in R)

回答済み

Nills van de Velde

2024年05月09日 13:07

• 
• 
• 

Hello there,

so I am encountering the issue that  the model seems to be infeasible as where it should not be. I am finding it difficult to pinpoint in why this model is returning this 'error' message - hopefully someone can point me towards the right direction

# Specify the file to read > # fileName = "example.txt"; > fileName = "small.txt"; > # Read the number of jobs > nProjects = scan(fileName, skip = 1, nlines = 1); Read 1 item > # Read the properties of the jobs > input = scan(fileName, skip = 3, nlines = nProjects); Read 30 items > durations = rep(-1, nProjects); > weights = rep(-1, nProjects); > deadlines = rep(-1, nProjects) > index = 1; > for(j in 1:nProjects) + { + durations[j]= input[index]; + deadlines[j] = input[index + 1]; + weights[j] = input[index + 2]; + index = index + 3; + } > rm(index, input, j, fileName) > deadlines [1] 14 13 11 15 7 19 10 20 15 13 > durations [1] 10 6 2 10 2 5 2 3 2 9 > weights [1] 2 4 4 1 2 2 1 3 4 4 > nProjects [1] 10 > # Calculate a suitable bigM, possibly a bit larger than the sum of all durations > bigM = sum(durations)+1 > # Initialize the MIP model > model <- MIPModel() %>% + # Define binary variables for project assignment to employees + add_variable(x[i, j], i = 1:2, j = 1:nProjects, type = "binary") %>% # x[i,j]: 1 if project j is assigned to employee i, otherwise 0 + # Define binary variables for sequencing of projects + add_variable(s[j, k], j = 1:nProjects, k = 1:nProjects, j != k, type = "binary") %>% # s[j,k]: 1 if project j is before project k, otherwise 0 + # Define continuous variables for project completion times + add_variable(C[j], j = 1:nProjects, type = "continuous", lb = 0, ub = sum(durations)) %>% # C[j]: Completion time of project j + # Define continuous variables for fines + add_variable(F[j], j = 1:nProjects, type = "continuous", lb = 0) %>% # F[j]: Fine for project j if it is late + + # Set the objective to minimize the sum of fines + set_objective(sum_expr(F[j], j = 1:nProjects), "min") %>% # Minimize the total fines across all projects + + # Assignment constraint: Each project is assigned to one employee + add_constraint(sum_expr(x[i, j], i = 1:2) == 1, j = 1:nProjects) %>% + + # Sequencing constraints: Ensure proper project ordering and completion time calculation + add_constraint(C[k] >= C[j] + durations[j] - bigM * (3 - s[j, k] - x[1, j] - x[1, k]), j = 1:nProjects, k = 1:nProjects, j != k) %>% + #add_constraint(C[k] >= C[j] + durations[j] - bigM * (3 - s[j, k] - x[2, j] - x[2, k]), j = 1:nProjects, k = 1:nProjects, j != k) %>% + + # Completion time initialization: Ensure project starts only after previous project's completion + add_constraint(C[j] >= sum_expr(durations[j] * x[i, j], i = 1:2), j = 1:nProjects) %>% + + # Fine calculation: Calculate fines based on project lateness + add_constraint(F[j] >= weights[j] * (C[j] - deadlines[j]), j = 1:nProjects) %>% + add_constraint(F[j] >= 0, j = 1:nProjects) %>% + + # Logical constraint for sequencing: Prevent circular project references + add_constraint(s[j, k] + s[k, j] <= 1, j = 1:nProjects, k = 1:nProjects, j != k) > model Mixed integer linear optimization problem Variables: Continuous: 20 Integer: 0 Binary: 110 Model sense: minimize Constraints: 220 > # Solve the model using Gurobi > library("gurobi") > params <- list(OutputFlag=1) #set solver options > result <- solve_model(model, with_ROI(solver = "gurobi", params)) Set parameter Username Academic license - for non-commercial use only - expires 2025-04-05 Gurobi Optimizer version 11.0.1 build v11.0.1rc0 (win64 - Windows 10.0 (19045.2)) CPU model: Intel(R) Core(TM) i5-7500 CPU @ 3.40GHz, instruction set [SSE2|AVX|AVX2] Thread count: 4 physical cores, 4 logical processors, using up to 4 threads Optimize a model with 220 rows, 130 columns and 710 nonzeros Model fingerprint: 0x0a330f6c Variable types: 20 continuous, 110 integer (110 binary) Coefficient statistics: Matrix range [1e+00, 5e+01] Objective range [1e+00, 1e+00] Bounds range [1e+00, 5e+01] RHS range [1e+00, 2e+02] Found heuristic solution: objective 0.0000000 Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units) Thread count was 1 (of 4 available processors) Solution count 1: 0 Optimal solution found (tolerance 1.00e-04) Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%

>

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:25

  This post is more than two 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 try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Simranjit Kaur

  • Gurobi Staff

  2024年05月10日 01:23

  Hi,

  Your Gurobi log does not report any error. The solver found one feasible solution with zero objective value (which means zero fine across all projects)

  Solution count 1: 0 

  This solution is also an optimal solution (within tolerances) for your model.

  Optimal solution found (tolerance 1.00e-04)

  Best regards,
  Simran

  0
• 

  Nills van de Velde

  2024年05月10日 07:46

  • 
  • 
  • 

  Hi,

  thank you for the feedback, this means that the MIP is not complete as a fine is expected due to the workload.

  I recon the StartTime is the issue.

  

  0

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