Hi! I am using Xpress to solve a MILP model.

By now, imposing an XPRS_MAXTIME of 60 seconds, the gap is equal to 47%. How to reduce it significantly with the optimizer?

Thank you in advance for any help.

Hi! I am using Xpress to solve a MILP model.

By now, imposing an XPRS_MAXTIME of 60 seconds, the gap is equal to 47%. How to reduce it significantly with the optimizer?

Thank you in advance for any help.

- 2 people found this helpful
Is it a hard requirement that you have to compute a solution and a gap within 60 seconds or can you spend more time for the computation? In general, the gap will decrease if you have more time. However, if you are solving a hard problem, then it is very likely that some after a certain amount of time the gap will only decrease extremely slowly. Even if the 60 seconds are a hard constraint, you could simply try what happens if you have more time. What is the gap after 10 minutes and after an hour? I guess that this will not help much, but it gives you an impression of how difficult your problem is.

- The most efficient way to significantly reduce the gap is by providing a good heuristic solution. Maybe you can formulate a model that is easier to solve and has a feasible region that is a subset of your original problem. For example, you could try to guess a good selection for your binary and integer variables, fix them, and use Xpress to compute a solution for this simplified subproblem.
- If you use "Big-M" formulations in your problem, check whether it is possible to choose smaller numbers.
- You can try the tuner to find better Xpress parameters for your problem. If you are already using Xpress 8.1, you can also use the new tuner functionality. (See the link below for more details.)
- Please have a look at the following discussion: Reducing computational times. You will find a lot of ideas about how to improve the computational time and hence also the gap.

- 1 person found this helpful
Note that you cannot really compare the gaps of two different objectives. If you take, for example, the zero function as objective and maximize or minimize it, then the solver will compute a solution with 0% relative gap and 0 absolute gap if it finds a solution. With respect to your original objective, this solution is just an arbitrary feasible solution and you don't get any information about how good it is with respect to the original objective. This is an extreme example, but it shows that it is difficult to compare the gaps of two different objectives.

Is it a hard requirement that you have to compute a solution and a gap within 60 seconds or can you spend more time for the computation? In general, the gap will decrease if you have more time. However, if you are solving a hard problem, then it is very likely that some after a certain amount of time the gap will only decrease extremely slowly. Even if the 60 seconds are a hard constraint, you could simply try what happens if you have more time. What is the gap after 10 minutes and after an hour? I guess that this will not help much, but it gives you an impression of how difficult your problem is.