MIPgap interpretation for a minimization problem

Hi everyone,

I am trying to minimize the total wastage space inside a container, however I am struggling to interpret the MIPgap returned by the HiGHS solver.

  1. My objective value is TotalWasteSpace = 2.05754e+10 and the absolute MIPgap is absmipgap=4.77382e+10. This does not make sense to me, because the absolute MIPgap tells me that if an optimal solution could be found, the best solution would be 2.05754e+10 - 4.77382e+10 and this gives me a negative value. There should not exist a negative value for the container space (volume)

  2. The relative MIPgap is relmipgap=2.32016, why is my relmipgap greater than 1?

Please kindly also find a screenshot of the return results in the attachment below.

Thank you for reading my questions.

Kind regards,
Hung-Yu Yang

To get help with this situation, add tech:outlev=1 to your highs_options string, and repeat the solve. This will produce a lot of detailed output. Copy all of the output into a file, and upload it here. Also if you have model and data files that can be uploaded, that would be useful.

For a minimization, the MIP gap is the BestSol value minus the BestBound value. At the end of the HiGHS run shown in the log file, BestSol is 24554200000 and BestBound is -27162825600. You should interpret these values as follows:

  • 24554200000 is the best objective value for any integer feasible solution that HiGHS found.

  • -27162825600 is the best lower bound that HiGHS was able to determine for the objective value.

HiGHS computes the lower bound from fractional feasible solutions that it finds at the nodes of the search tree. (A fractional feasible solution satisfies all of the constraints, but some of its binary variables have values that are fractions between 0 and 1.) The lower bound can be negative for your problem, because there are many fractional feasible solutions that have negative objective values.

Even though the lower bound is negative at some point in the HiGHS run, that does not mean that the optimal value can be negative. If the actual minimum objective value for your problem has to be nonnegative, then if you run HiGHS long enough, the lower bound will increase to a nonnegative value. The run will end when the lower and upper bounds are both nonnegative and are within the gap tolerance (0.01%). But when you end the run after 360 seconds, the most that you can say is that the optimal objective value is \leq 24554200000.

Note also that AMPL’s if-then operator only returns a number, and thus cannot be used to model a constraint. Instead, you should use the ==> (“implies”) operator. For example, instead of

subject to Constraint11{s in stack}:
	if x[s]=1 then

you should write

subject to Constraint11{s in stack}:
	x[s]=1 ==>

(There are 4 other constraints that need to be fixed like this.)

Also, setting cvt:bigM=16000 may lead to lower bounds that are very low — even negative, as you have seen. You may be able to get better bounds by removing cvt:bigM=16000 from highs_options, and instead putting good upper bounds on all of the variables that appear in the ==> constraints. These upper bounds do not have to be the same for all variables.

Thank you very much for your detailed reply. I will go though them now.