Topic
• 4 replies
• Latest Post - ‏2013-07-04T19:49:00Z by Matthew Tsang
Matthew Tsang
3 Posts

# Pinned topic Fasten Optimisation process of a MILP problem

‏2013-07-04T01:43:25Z |

Hello,

I have been working on a problem with some boolean and float decision variables. The constraints are mostly linear programming related. The existence of the boolean variables, however, seems to have made the optimizer to solve the problem with MILP instead of the simple and faster LP.  This hugely restricts the size of my model and I am trying to find different means to make my model to run in a more efficient way.

I wonder if approximation algorithm is a sensible solution to my issue. Since I am a rookie on this topic, I have chosen a book to read (which I can post the official link here if it is not against the rule of this forum). The book seems to be mostly about set cover problems and I wonder if this actually covers most approximation algorithm. In addition, I wonder if there are alternative ways to solve the MILP in a quicker way.

Matthew

• TobiasAchterberg
8 Posts

#### Re: Fasten Optimisation process of a MILP problem

‏2013-07-04T07:45:20Z

Linear programs can be solved in polynomial time, while MILPs are NP-hard (which means that nobody knows of a polynomial algorithm and it is likely that no such thing exists). So, you are facing a severe theoretical difference between the two problem classes. MILP is just much more difficult.

The question now is why you need the binary variables in your model. If the practical model that you want to solve asks for yes/no decisions, than there is not much you can do about: your problem contains combinatorial decisions so you are in the world of MILP. If you want to find an optimal solution to your MILP model, then the branch-and-cut approach that CPLEX implements is the current state-of-the-art. If you are happy with just some reasonably good solution and do not care about optimality, you can think of heuristic approaches, either a MILP based one or a problem specific one.

Tobias

• TobiasAchterberg
8 Posts

#### Re: Fasten Optimisation process of a MILP problem

‏2013-07-04T17:31:11Z

Thank you for your informative reply. By reading the Cplex manual, it seems to me that branch and cut approach treats ,for example, binary integers in a optimisation problem as continuous values, 0-1 so that the problem can be solved with a series of LPs. Extra constraints are then applied to these LPs.  Under these constraints, the optimizer would in effect accept the solution if and only if the original boolean variables are found to be 0 or 1.

Please correct me if my interpretation is incorrect. However, base on my understanding, it seems that the optimizer is only treating a slightly larger LP problem.  But in fact, the required solving time still grows exponentially when the size of the model increases, which builds up my new confusion.

Matthew

MILPs are solved with a tree search algorithm that is called branch-and-bound. Additional, cutting plane separation is applied to improve performance of this tree search which leads to the name branch-and-cut.

The basic tree search algorithm is rather simple: one solves the LP relaxation of the MILP (which is the problem without the integrality restrictions) and gets a solution to this LP. If by coincidence all variables that should be integer have an integral LP solution value, then we are done: we have found an optimal integer solution to the MILP. If not (which is the typical case) then one picks one variable xj from the set of integer variables with fractional LP value xj* and creates two sub-problems: one by adding the restriction xj <= floor(xj*) and one by adding the restriction xj >= ceil(xj*). This yields two child nodes of the root node. Now one applies the same approach recursively on the children. This yields a search tree that has to be processed.

If your problem contains n binary variables (plus an arbitrary number of continuous variables), then the search tree has in principle 2^n leaf nodes that have to be processed. This is where the exponential nature of the algorithm comes from. Now the main trick to get a high performance algorithm like CPLEX is to find clever ways to discard many of those nodes without having to actually process them. This works often (but not always) very well so that CPLEX can solve many problem instances with a large number of integer restricted variables, even though in the worst case the search tree could grow exponentially.

Tobias

• TobiasAchterberg
8 Posts

#### Re: Fasten Optimisation process of a MILP problem

‏2013-07-04T07:45:20Z

Linear programs can be solved in polynomial time, while MILPs are NP-hard (which means that nobody knows of a polynomial algorithm and it is likely that no such thing exists). So, you are facing a severe theoretical difference between the two problem classes. MILP is just much more difficult.

The question now is why you need the binary variables in your model. If the practical model that you want to solve asks for yes/no decisions, than there is not much you can do about: your problem contains combinatorial decisions so you are in the world of MILP. If you want to find an optimal solution to your MILP model, then the branch-and-cut approach that CPLEX implements is the current state-of-the-art. If you are happy with just some reasonably good solution and do not care about optimality, you can think of heuristic approaches, either a MILP based one or a problem specific one.

Tobias

• Matthew Tsang
3 Posts

#### Re: Fasten Optimisation process of a MILP problem

‏2013-07-04T14:51:52Z

Linear programs can be solved in polynomial time, while MILPs are NP-hard (which means that nobody knows of a polynomial algorithm and it is likely that no such thing exists). So, you are facing a severe theoretical difference between the two problem classes. MILP is just much more difficult.

The question now is why you need the binary variables in your model. If the practical model that you want to solve asks for yes/no decisions, than there is not much you can do about: your problem contains combinatorial decisions so you are in the world of MILP. If you want to find an optimal solution to your MILP model, then the branch-and-cut approach that CPLEX implements is the current state-of-the-art. If you are happy with just some reasonably good solution and do not care about optimality, you can think of heuristic approaches, either a MILP based one or a problem specific one.

Tobias

Thank you for your informative reply. By reading the Cplex manual, it seems to me that branch and cut approach treats ,for example, binary integers in a optimisation problem as continuous values, 0-1 so that the problem can be solved with a series of LPs. Extra constraints are then applied to these LPs.  Under these constraints, the optimizer would in effect accept the solution if and only if the original boolean variables are found to be 0 or 1.

Please correct me if my interpretation is incorrect. However, base on my understanding, it seems that the optimizer is only treating a slightly larger LP problem.  But in fact, the required solving time still grows exponentially when the size of the model increases, which builds up my new confusion.

Matthew

Updated on 2013-07-04T15:03:04Z at 2013-07-04T15:03:04Z by Matthew Tsang
• TobiasAchterberg
8 Posts

#### Re: Fasten Optimisation process of a MILP problem

‏2013-07-04T17:31:11Z

Thank you for your informative reply. By reading the Cplex manual, it seems to me that branch and cut approach treats ,for example, binary integers in a optimisation problem as continuous values, 0-1 so that the problem can be solved with a series of LPs. Extra constraints are then applied to these LPs.  Under these constraints, the optimizer would in effect accept the solution if and only if the original boolean variables are found to be 0 or 1.

Please correct me if my interpretation is incorrect. However, base on my understanding, it seems that the optimizer is only treating a slightly larger LP problem.  But in fact, the required solving time still grows exponentially when the size of the model increases, which builds up my new confusion.

Matthew

MILPs are solved with a tree search algorithm that is called branch-and-bound. Additional, cutting plane separation is applied to improve performance of this tree search which leads to the name branch-and-cut.

The basic tree search algorithm is rather simple: one solves the LP relaxation of the MILP (which is the problem without the integrality restrictions) and gets a solution to this LP. If by coincidence all variables that should be integer have an integral LP solution value, then we are done: we have found an optimal integer solution to the MILP. If not (which is the typical case) then one picks one variable xj from the set of integer variables with fractional LP value xj* and creates two sub-problems: one by adding the restriction xj <= floor(xj*) and one by adding the restriction xj >= ceil(xj*). This yields two child nodes of the root node. Now one applies the same approach recursively on the children. This yields a search tree that has to be processed.

If your problem contains n binary variables (plus an arbitrary number of continuous variables), then the search tree has in principle 2^n leaf nodes that have to be processed. This is where the exponential nature of the algorithm comes from. Now the main trick to get a high performance algorithm like CPLEX is to find clever ways to discard many of those nodes without having to actually process them. This works often (but not always) very well so that CPLEX can solve many problem instances with a large number of integer restricted variables, even though in the worst case the search tree could grow exponentially.

Tobias

• Matthew Tsang
3 Posts

#### Re: Fasten Optimisation process of a MILP problem

‏2013-07-04T19:49:00Z

MILPs are solved with a tree search algorithm that is called branch-and-bound. Additional, cutting plane separation is applied to improve performance of this tree search which leads to the name branch-and-cut.

The basic tree search algorithm is rather simple: one solves the LP relaxation of the MILP (which is the problem without the integrality restrictions) and gets a solution to this LP. If by coincidence all variables that should be integer have an integral LP solution value, then we are done: we have found an optimal integer solution to the MILP. If not (which is the typical case) then one picks one variable xj from the set of integer variables with fractional LP value xj* and creates two sub-problems: one by adding the restriction xj <= floor(xj*) and one by adding the restriction xj >= ceil(xj*). This yields two child nodes of the root node. Now one applies the same approach recursively on the children. This yields a search tree that has to be processed.

If your problem contains n binary variables (plus an arbitrary number of continuous variables), then the search tree has in principle 2^n leaf nodes that have to be processed. This is where the exponential nature of the algorithm comes from. Now the main trick to get a high performance algorithm like CPLEX is to find clever ways to discard many of those nodes without having to actually process them. This works often (but not always) very well so that CPLEX can solve many problem instances with a large number of integer restricted variables, even though in the worst case the search tree could grow exponentially.

Tobias

I see.  So the branch-and-bound is a simple approach while the cutting part is operated with an implicit and clever (and unknown) algorithm by CPLEX.

That is a very well presented explanation. Thank you for your help, Tobias.

Matthew