How to give the initial solution
Answered
Hello.
I am dealing with a problem of 25 nurses, 30 days,
3 shifts.
The variables are x[i,j,k], which are 0-1 variables. i is the date, j is the nurse number. k is D for day shift, E for night shift, N for night shift, O for other duties, R for day off.
If x[3,1,D]=1, we know that nurse 1 is on day shift on the 3rd.
So I thought of solving the problem of 25 nurses, 21 days, 3 shifts as a reduced problem, and giving that solution as the initial solution in an mst file.
The variable definitions should be the same, but the initial solution is ignored.
The MST file looks like this:
x[1,1,D] 1
x[1,2,D] 1
The peripheral program that reads the initial solution is as follows:
# coding:utf-8
from gurobipy import *
import time
import os
# Time measurement
start_time = time.time()
# Define a model for a 30-day schedule with 25 nurses
M=range(1,26)
J=range(1,31)
J1=range(-5,31)
K=['D','N','E','R','O']
K1=['D','N','E','R']
K2=['D','N','E','O']
K3=['D','N','E']
# Create a 30-day model
m=Model("Adjustment parameters")
x=m.addVars(M,J1,K,vtype="B")
m.update()
# Load the mst file
file_name = f'initial_values_3.mst'
if not os.path.exists(file_name):
print(f"File {file_name} does not exist.")
try:
# Read mst file
m.read(file_name)
print(f"Processing {file_name}") # Output the file currently being processed
except GurobiError as e:
print(f"Error reading {file_name}: {str(e)}")
Could you please give me some comments or advice?
Thank you in advance.
-
Hi Kanato,
It seems you are missing the m.optimize() command after the mip start file is read (m.read(file_name). For details on how to provide a mip start to a model, please see the article: How do I use MIP starts?
Best regards,
Simran0 -
Thank you for your reply.
The initial values were loaded correctly and MIPstart was executed.
However, the calculation time is longer than expected, and the purpose of shortening the calculation time by specifying initial values has not been achieved. Initial values were specified for 21 days, 25 days, etc.
If the goal is to shorten the calculation time, is ① this kind of process useless?
Or, ② are the initial values specified incorrectly? Regarding ②, when I ran the program, I received a warning like this: Warning: Completing partial solution with 12204 unfixed non-continuous variables out of 12829. Could this be the cause?
Below is the console screen when it was executed. I would appreciate any advice, no matter how trivial. Thank you in advance.
Optimize a model with 20434 rows, 12829 columns and 97539 nonzeros
Model fingerprint: 0x05057b09
Variable types: 0 continuous, 12829 integer (12750 binary)
Coefficient statistics:
Matrix range [1e+00, 8e+00]
Objective range [1e+00, 1e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 2e+02]Warning: Completing partial solution with 12204 unfixed non-continuous variables out of 12829
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 5s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 10s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 15s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 20s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 25s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 30s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 35s
Processing user MIP start: 57 nodes explored in subMIP, total elapsed time 40s
Processing user MIP start: 195 nodes explored in subMIP, total elapsed time 45s
User MIP start produced solution with objective 408 (48.87s)
Processing user MIP start: 424 nodes explored in subMIP, total elapsed time 50s
Loaded user MIP start with objective 408
Processed MIP start in 52.25 seconds (51.53 work units)Presolve removed 12131 rows and 10182 columns
Presolve time: 0.35s
Presolved: 8303 rows, 2647 columns, 38135 nonzeros
Variable types: 0 continuous, 2647 integer (2584 binary)Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 1.0500000e+02 2.493500e+03 0.000000e+00 53s
8554 1.0700000e+02 0.000000e+00 0.000000e+00 55sRoot relaxation: objective 1.070000e+02, 8554 iterations, 2.21 seconds (1.73 work units)
Total elapsed time = 56.51s (DegenMoves)Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 107.00000 0 662 408.00000 107.00000 73.8% - 59s
0 0 107.00000 0 884 408.00000 107.00000 73.8% - 60s0 -
Hi Kanato,
Providing a good start solution can potentially help in speeding the solve time (but there is no guarantee).
Your model has 12829 integer variables. The warning in the log
Warning: Completing partial solution with 12204 unfixed non-continuous variables out of 12829
means that your partial mip start fixes only 625 integer variables out of 12829, leading to a challenging subproblem that is almost as difficult as the original model. As you can see in the log, the solver had to explore 424 nodes and spend almost 50 seconds to complete your partial mip start and find a feasible solution. If possible, please provide a more complete solution in the MIP start by fixing a larger portion of the integer variables.
Best regards,
Simran0
Please sign in to leave a comment.
Comments
3 comments