User Tools

Site Tools


Multiple solutions of a MIP

I was wondering how you would code a Mixed Integer Linear Program, so that you would be able to obtain all solutions with an objective value less than some predetermined value for a minimisation problem.

Obtaining all solutions (with objective in a particular interval) of a MIP is not an easy task. If you have continous variables in the MIP there may be even infinite many optimal solutions. In this case there is no efficient general way. You may check books on 'sensitivity analysis' of LPs and MIP.

If your MIP consists of binary/integer variables only, there is a possible way for your problem: You solve the original problem in order to get one optimal solution. Then you add a new constraint to 'cut off' the optimal solution and comes up with the next best solution. You do this loop until the objective of the solution becomes to small. An example of this 'cutting plane' method can be found in the model library (model icut)

From the GAMS IDE choose file→Open in GAMS Model Library→Model icut and run the model (by pressing F9). From a command line (DOS box or UNIX shell) call

		gamslib icut 
		gams icut

If you are just interested to obtain a list of best integer solutions of your MIP, please check that entry

solver/multiple_solutions_of_a_mip.txt · Last modified: 2007/07/31 14:21 (external edit)