Originally posted by: exDev

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!

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.

Originally posted by: exDev

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.