Topic
  • 3 replies
  • Latest Post - ‏2013-05-01T09:23:29Z by DanielJunglas
exDev
exDev
2 Posts

Pinned topic Approximate solutions using IBM optimization tools

‏2013-04-17T08:36:58Z |

Hello all,  I would like to know whether it is possible to get approximate results using IBM optimization tools (CPLEX, ILOG CP etc).

The reason to search for such an option is that in my optimization problem, I have limited time to solve the problem.

Moreover, I would like to have some theoritical guarantees that how much far the approximate solution is from the optimal solution? What possibilities do I have using the exisiting tools?  

Thanks in advance for taking out time for this question and hope to hear from you!

  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Approximate solutions using IBM optimization tools

    ‏2013-04-30T08:13:03Z  

    What type of problems do you need to solve?

    If you solve for example (mixed) integer programs using the CPLEX Optmizer then this will produce an absolute and a relative mip gap. This gap provides a theoretical guarantee for the maximum difference between the best known solution and the (unknown) optimal solution. Maybe this chapter in the user manual can help you to understand what the gap information means and how it provides a guarantee for the quality of the current solution.

  • exDev
    exDev
    2 Posts

    Re: Approximate solutions using IBM optimization tools

    ‏2013-04-30T18:06:13Z  

    What type of problems do you need to solve?

    If you solve for example (mixed) integer programs using the CPLEX Optmizer then this will produce an absolute and a relative mip gap. This gap provides a theoretical guarantee for the maximum difference between the best known solution and the (unknown) optimal solution. Maybe this chapter in the user manual can help you to understand what the gap information means and how it provides a guarantee for the quality of the current solution.

    I am trying to solve a  traditional Job Shop Scheduling problem. Given a problem instance, the scheduler must provide a solution (preferably an optimal one) in a limited time period. The problem can be seen as online or dynamic job shop scheduling. A way to get such a schedule is to set time limits and get a solution. However, I am searching for techniques which some how provide a guarantee that how fast they will converge to optimality or how far the provided solution is from an optimal solution. Do you know any such technique?

     

    I have modeled my problem both using MIP and CP. I will go through the chapter you recommended. Thanks a lot for your response. 

    Updated on 2013-04-30T18:18:24Z at 2013-04-30T18:18:24Z by exDev
  • DanielJunglas
    DanielJunglas
    145 Posts

    Re: Approximate solutions using IBM optimization tools

    ‏2013-05-01T09:23:29Z  
    • exDev
    • ‏2013-04-30T18:06:13Z

    I am trying to solve a  traditional Job Shop Scheduling problem. Given a problem instance, the scheduler must provide a solution (preferably an optimal one) in a limited time period. The problem can be seen as online or dynamic job shop scheduling. A way to get such a schedule is to set time limits and get a solution. However, I am searching for techniques which some how provide a guarantee that how fast they will converge to optimality or how far the provided solution is from an optimal solution. Do you know any such technique?

     

    I have modeled my problem both using MIP and CP. I will go through the chapter you recommended. Thanks a lot for your response. 

    If I understand correctly you are looking for two independent things:

    1. "how far the provided solution is from an optimal solution" -- this is exactly the information that is provided by the MIP gap. When solving a MIP you get a primal bound (the objective function of the best feasible solution found so far) and a dual bound (a bound for the best possible solutions). These two bounds give the maximum distance of the current best feasible solution from the optimal solution.
    2. "how fast they will converge to optimality" -- a MIP solver does not offer this type of guarantees. In fact, it is the other way around, a MIP solver may take exponential time to find the optimal solution since MIP is NP hard. There are concepts like (F)PTAS or APX-hardness that cover approximation of NP-hard problems. You could check the literature if there are any results for your problem type.