Skip to main content

I am currently working on a university examination timetabling problem to produce an effective final exam schedule that considers student and lecturer complaints as well as basic scheduling requirements. Upon execution, AIMMS provided a solution with 99.02% optimality, indicating an optimality gap of 0.08% (showed in the progress window). I have a few questions to better understand this result.


(1) What exactly does it mean by optimality gap. Does a 99.02% optimality indicates that the solution meets all hard constraints included and is 99.02% optimal relative to an ideal solution? How is this percentage determined. We are curious about whether AIMMS has checked every single hard constraint. 


(2) Our problems involve 3 objective functions. We are interested to know how AIMMS handles multiple objective functions. Does it calculate each objective function separately or simultaneously? How does this impact the overall optimality percentage? Which objective function might AIMMS be prioritizing.


(3) Regarding the 99.02% optimality, we would like to know if this means AIMMS has evaluated 99.02% of the best possible answers for the exams. If the optimality were 100%, would that indicate all possible answers have been checked and are optimal?


(4) Regarding the 0.08 gap, is this gap a result of an ongoing check? Is AIMMS providing the best solution, and is this gap merely for verification to see if any changes occur?


(5) If there are 100 exams and we achieve 99% optimality, has AIMMS checked 99 out of 100 possible optimal answers, or does this imply something else?

 

Thankyou.

 

With regards to the gap, I am assuming you are using an Integer Linear Programming formulation.

 

In that case, the gap comes from the calculation between the lower bound calculated by removing all integrality constraints (relaxed problem) and an actual integer solution you have. By removing the integrality constraints, you make the problem easier to solve and the solution to this easier problem provides you a lowerbound (assuming a minimization problem) to the actual problem: you know that there will not exist a solution better than this.

A solver typically will not have to go through ALL possible solutions, but it goes through the solution space using a branch-and-bound tree, where it will be able to sometimes prune certain parts of the tree because due to the bound information you know you can not find a better solution in that area of the tree anymore.

If you are indeed working with an integer linear program, would recommend to do a search on branch-and-bound to get an idea on how the process works and where the gaps/bounds come from.

 

Regarding the multiple objectives, not sure how you did that. If you look at https://documentation.aimms.com/language-reference/optimization-modeling-components/implementing-advanced-algorithms-for-mathematical-programs/multi-objective-optimization.html you will see that there are two ways of dealing with multiple objectives: lexicographic and blended. If you do lexicographic, the solver will first spend time on optimizing the first objective, then the second, then the third, etc. If you use blended, you solve for all objectives simultaneously because they are all blended together using weights.

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