Skip to main content

Hello,

I am currently working on solving a University Examination Timetabling Problem (UETP) using the Binary Integer Programming (BIP) method in AIMMS. My model includes two soft constraints, where preference values are restricted to integers from 1 to 5 (i.e., 5, 4, 3, 2, 1).

After running the model in AIMMS, I obtained the following results:

  • Best LP Bound: 4080.487042

  • Best Solution: 4041

  • Gap: 0.98%

From my understanding:

  • The Best LP Bound represents the theoretical lower bound from the linear relaxation of the integer program.

  • The Best Solution is the best feasible (integer) solution found so far.

  • When the Gap reaches 0%, the Best Solution should equal the Best LP Bound.

My question is:
Since I am solving a binary integer problem, how is it possible that when the gap reaches 0%, the Best Solution appears as a decimal value (e.g., 4080.487042)? Shouldn’t the solution remain strictly integer (since it’s binary), and therefore the objective value also be an integer?

 

Any clarification would be greatly appreciated. Thank you!

Hi ​@Wanie Saidi. What objective value is shown in the solver log once the solver is finished (and reached a gap of 0%)? Can you share the solver log file?

Just to clarify, actually, I have not achieved a 0% gap in my current research. The best results I’ve obtained so far are:

  • Best LP Bound: 4080.487042

  • Best Solution: 4041

  • Gap: 0.98%

So unfortunately, I’m unable to provide the exact objective value from the solver log at 0% gap, because I haven’t reached that point yet.

However, what I’m trying to understand is this:

If I eventually achieve a 0% gap, will the Best Solution be equal to the Best LP Bound and if so, will that objective value still be a decimal (e.g., 4080.487042) even though the model is a Binary Integer Program?

I understand that the Best LP Bound comes from the LP relaxation, and that decimal values are expected there. But in a BIP model, shouldn’t the final objective value be an integer as well, assuming all variables are binary and the objective function uses integer coefficients?

That’s the part I’m hoping to clarify.

Thanks again for your help.

Reply


Terms & Conditions

Didn't find what you were looking for? Try searching on our documentation pages:

AIMMS Developer & PRO | AIMMS How-To | AIMMS SC Navigator