Decision Optimization

I'm working on a MILP scheduling problem for assigning elements to slots based on some business rules.   Some of the elements' attributes change over time, therefore we have to re-compute the schedule.  

Our problem is very large for example some of them have hundreds of millions of decision variables or more.

I would like to improve our performance by feeding the a prior solution as a warm start.  In CPLEX I see that you can set the DV values as a sort of initial basis.  My question is, are the previous solution's values sufficient to provide my new model a benefit, or is there more I need to do.  Also, the number of DVs changes over time since elements can be added or removed from the domain.  

Any tips or guidance here would be much appreciated!

------------------------------
Karl Schelhammer
------------------------------

#DecisionOptimization

Providing values for some or all decision variables and for one additional argument that I will describe below should be sufficient. It is fine to omit values for variables that have been added since the last solution (i.e., you do not need to guess values). Values for variables that have been dropped since the last solution should definitely not be provided; CPLEX does not like references to variables not in the current model.

Given a partial, not necessarily feasible, starting solution, CPLEX can either ignore it or attempt to fix it (and then ignore it if repairs fail). This brings me to the (optional) effort argument. You did not specify an API, so I will describe it in terms of the Java API. You want to choose one of the overloads of IloCplex.addMIPStart() that includes the effort argument, which is an instance of IloCplex.MIPStartEffort. The default value (if omitted) gives CPLEX freedom to expend as much or as little effort repairing the MIP start as it deems appropriate. Since your starting solution is likely to be missing variables and may well be infeasible, I would suggest using the value IloCplex.MIPStartEffort.Repair, which as the name suggests tells CPLEX to try to repair the solution (if needed). There is a separate parameter (Java name IloCplex.Param.MIP.Limits.RepairTries) that is not an argument to addMIPStart and instead is set as other parameters are set. This governs how much work CPLEX does trying to fix the starting solution. The default is again to let CPLEX decide, but you can set it to a positive integer value to dictate the number of attempts. (What constitutes a reasonable number of attempts for you will no doubt be a matter of experimentation.)

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Tue September 08, 2020 11:23 AM
From: Karl Schelhammer
Subject: Questions about MILP warm start.

I'm working on a MILP scheduling problem for assigning elements to slots based on some business rules.   Some of the elements' attributes change over time, therefore we have to re-compute the schedule.  

Our problem is very large for example some of them have hundreds of millions of decision variables or more.

I would like to improve our performance by feeding the a prior solution as a warm start.  In CPLEX I see that you can set the DV values as a sort of initial basis.  My question is, are the previous solution's values sufficient to provide my new model a benefit, or is there more I need to do.  Also, the number of DVs changes over time since elements can be added or removed from the domain.  

Any tips or guidance here would be much appreciated!

------------------------------
Karl Schelhammer
------------------------------

#DecisionOptimization

Thanks for the helpful advice Paul.  We have gone ahead and implemented the warm start using the python API.

So far we have not seen any benefit, although I am not sure if the algorithm is even paying attention to our warm start.  I am providing the warm start values using the warmstart.add_var_value(variable, value) api call.

We leveraged the example here to develop our code:

https://github.com/AlexFleischerParis/zoodocplex/blob/master/zoowarmstartapi.py

I don't see in our logs any indication that we are using the warmstart.  In the example above they say to look for something like:

1 of 1 MIP starts provided solutions. MIP start 'm1' defined initial solution with objective 4000.0000.​

Are there any other examples out there for warmstarting with the Python API or other things I can check to make sure its working properly?

------------------------------
Karl Schelhammer
------------------------------

Original Message:
Sent: Tue September 08, 2020 05:11 PM
From: Paul Rubin
Subject: Questions about MILP warm start.

Providing values for some or all decision variables and for one additional argument that I will describe below should be sufficient. It is fine to omit values for variables that have been added since the last solution (i.e., you do not need to guess values). Values for variables that have been dropped since the last solution should definitely not be provided; CPLEX does not like references to variables not in the current model.

Given a partial, not necessarily feasible, starting solution, CPLEX can either ignore it or attempt to fix it (and then ignore it if repairs fail). This brings me to the (optional) effort argument. You did not specify an API, so I will describe it in terms of the Java API. You want to choose one of the overloads of IloCplex.addMIPStart() that includes the effort argument, which is an instance of IloCplex.MIPStartEffort. The default value (if omitted) gives CPLEX freedom to expend as much or as little effort repairing the MIP start as it deems appropriate. Since your starting solution is likely to be missing variables and may well be infeasible, I would suggest using the value IloCplex.MIPStartEffort.Repair, which as the name suggests tells CPLEX to try to repair the solution (if needed). There is a separate parameter (Java name IloCplex.Param.MIP.Limits.RepairTries) that is not an argument to addMIPStart and instead is set as other parameters are set. This governs how much work CPLEX does trying to fix the starting solution. The default is again to let CPLEX decide, but you can set it to a positive integer value to dictate the number of attempts. (What constitutes a reasonable number of attempts for you will no doubt be a matter of experimentation.)

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Tue September 08, 2020 11:23 AM
From: Karl Schelhammer
Subject: Questions about MILP warm start.

I'm working on a MILP scheduling problem for assigning elements to slots based on some business rules.   Some of the elements' attributes change over time, therefore we have to re-compute the schedule.  

Our problem is very large for example some of them have hundreds of millions of decision variables or more.

I would like to improve our performance by feeding the a prior solution as a warm start.  In CPLEX I see that you can set the DV values as a sort of initial basis.  My question is, are the previous solution's values sufficient to provide my new model a benefit, or is there more I need to do.  Also, the number of DVs changes over time since elements can be added or removed from the domain.  

Any tips or guidance here would be much appreciated!

------------------------------
Karl Schelhammer
------------------------------
#DecisionOptimization

Karl,

I usually tell if a warm start was used by looking for the line you highlighted in the log file (early on in the log, before the root is solved). The Java API has a getNMIPStarts() method that will tell you how many MIP starts are associated with a given model. I assume the Python API has a version of it as well.

If you're not seeing a line about MIP starts in the log, the first thing to do is make sure you have a line that calls add_mip_start() (line 12 in Alex's code sample) and that it executes.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Wed September 16, 2020 01:35 PM
From: Karl Schelhammer
Subject: Questions about MILP warm start.

Thanks for the helpful advice Paul.  We have gone ahead and implemented the warm start using the python API.

So far we have not seen any benefit, although I am not sure if the algorithm is even paying attention to our warm start.  I am providing the warm start values using the warmstart.add_var_value(variable, value) api call.

We leveraged the example here to develop our code:

https://github.com/AlexFleischerParis/zoodocplex/blob/master/zoowarmstartapi.py

I don't see in our logs any indication that we are using the warmstart.  In the example above they say to look for something like:

1 of 1 MIP starts provided solutions.MIP start 'm1' defined initial solution with objective 4000.0000.​

Are there any other examples out there for warmstarting with the Python API or other things I can check to make sure its working properly?

------------------------------
Karl Schelhammer

Original Message:
Sent: Tue September 08, 2020 05:11 PM
From: Paul Rubin
Subject: Questions about MILP warm start.

Providing values for some or all decision variables and for one additional argument that I will describe below should be sufficient. It is fine to omit values for variables that have been added since the last solution (i.e., you do not need to guess values). Values for variables that have been dropped since the last solution should definitely not be provided; CPLEX does not like references to variables not in the current model.

Given a partial, not necessarily feasible, starting solution, CPLEX can either ignore it or attempt to fix it (and then ignore it if repairs fail). This brings me to the (optional) effort argument. You did not specify an API, so I will describe it in terms of the Java API. You want to choose one of the overloads of IloCplex.addMIPStart() that includes the effort argument, which is an instance of IloCplex.MIPStartEffort. The default value (if omitted) gives CPLEX freedom to expend as much or as little effort repairing the MIP start as it deems appropriate. Since your starting solution is likely to be missing variables and may well be infeasible, I would suggest using the value IloCplex.MIPStartEffort.Repair, which as the name suggests tells CPLEX to try to repair the solution (if needed). There is a separate parameter (Java name IloCplex.Param.MIP.Limits.RepairTries) that is not an argument to addMIPStart and instead is set as other parameters are set. This governs how much work CPLEX does trying to fix the starting solution. The default is again to let CPLEX decide, but you can set it to a positive integer value to dictate the number of attempts. (What constitutes a reasonable number of attempts for you will no doubt be a matter of experimentation.)

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Tue September 08, 2020 11:23 AM
From: Karl Schelhammer
Subject: Questions about MILP warm start.

I'm working on a MILP scheduling problem for assigning elements to slots based on some business rules.   Some of the elements' attributes change over time, therefore we have to re-compute the schedule.  

Our problem is very large for example some of them have hundreds of millions of decision variables or more.

I would like to improve our performance by feeding the a prior solution as a warm start.  In CPLEX I see that you can set the DV values as a sort of initial basis.  My question is, are the previous solution's values sufficient to provide my new model a benefit, or is there more I need to do.  Also, the number of DVs changes over time since elements can be added or removed from the domain.  

Any tips or guidance here would be much appreciated!

------------------------------
Karl Schelhammer
------------------------------
#DecisionOptimization

In the log you should definitely a line about MIP starts either providing or not providing a warm start. If you don't see this line then something is wrong.
You can also set the solution limit parameter to 1. With this, if you provide a warmstart and CPLEX finds a feasible solution from that warmstart then it should stop very early in the solution process.

So like Paul suggested, the very first thing to do is to make sure you actually submit the warmstart to the solver.

If you keep running into issues then it would be good if you could provide a short code example that fails for you. From that it would be easier to tell what may be going wrong on your side.

------------------------------
Daniel Junglas
------------------------------

Original Message:
Sent: Wed September 16, 2020 01:35 PM
From: Karl Schelhammer
Subject: Questions about MILP warm start.

Thanks for the helpful advice Paul.  We have gone ahead and implemented the warm start using the python API.

So far we have not seen any benefit, although I am not sure if the algorithm is even paying attention to our warm start.  I am providing the warm start values using the warmstart.add_var_value(variable, value) api call.

We leveraged the example here to develop our code:

https://github.com/AlexFleischerParis/zoodocplex/blob/master/zoowarmstartapi.py

I don't see in our logs any indication that we are using the warmstart.  In the example above they say to look for something like:

1 of 1 MIP starts provided solutions.MIP start 'm1' defined initial solution with objective 4000.0000.​

Are there any other examples out there for warmstarting with the Python API or other things I can check to make sure its working properly?

------------------------------
Karl Schelhammer

Original Message:
Sent: Tue September 08, 2020 05:11 PM
From: Paul Rubin
Subject: Questions about MILP warm start.

Providing values for some or all decision variables and for one additional argument that I will describe below should be sufficient. It is fine to omit values for variables that have been added since the last solution (i.e., you do not need to guess values). Values for variables that have been dropped since the last solution should definitely not be provided; CPLEX does not like references to variables not in the current model.

Given a partial, not necessarily feasible, starting solution, CPLEX can either ignore it or attempt to fix it (and then ignore it if repairs fail). This brings me to the (optional) effort argument. You did not specify an API, so I will describe it in terms of the Java API. You want to choose one of the overloads of IloCplex.addMIPStart() that includes the effort argument, which is an instance of IloCplex.MIPStartEffort. The default value (if omitted) gives CPLEX freedom to expend as much or as little effort repairing the MIP start as it deems appropriate. Since your starting solution is likely to be missing variables and may well be infeasible, I would suggest using the value IloCplex.MIPStartEffort.Repair, which as the name suggests tells CPLEX to try to repair the solution (if needed). There is a separate parameter (Java name IloCplex.Param.MIP.Limits.RepairTries) that is not an argument to addMIPStart and instead is set as other parameters are set. This governs how much work CPLEX does trying to fix the starting solution. The default is again to let CPLEX decide, but you can set it to a positive integer value to dictate the number of attempts. (What constitutes a reasonable number of attempts for you will no doubt be a matter of experimentation.)

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Original Message:
Sent: Tue September 08, 2020 11:23 AM
From: Karl Schelhammer
Subject: Questions about MILP warm start.

I'm working on a MILP scheduling problem for assigning elements to slots based on some business rules.   Some of the elements' attributes change over time, therefore we have to re-compute the schedule.  

Our problem is very large for example some of them have hundreds of millions of decision variables or more.

I would like to improve our performance by feeding the a prior solution as a warm start.  In CPLEX I see that you can set the DV values as a sort of initial basis.  My question is, are the previous solution's values sufficient to provide my new model a benefit, or is there more I need to do.  Also, the number of DVs changes over time since elements can be added or removed from the domain.  

Any tips or guidance here would be much appreciated!

------------------------------
Karl Schelhammer
------------------------------
#DecisionOptimization