# # A hands on maple session to solve an ILP using Gomory's algorithm # # min -4 x1+ 7x2 st. x2 <= 1, -2 x1 + x2 <= 2 , 4 x1 - x2 <= 10 # all variables integer and non-negative with(simplex); # set up the linear program with slacks added # consts = constraints, obj = objective function # dic = is a dictionary with both consts and obj consts:={x3 = 1 - x2, x4 = 2 + 2*x1 - x2, x5 = 10 - 4*x1 + x2}; obj:={z = -4*x1 + 7* x2}; dic:= consts union obj; # start one iteration of Gomory's algorithm # solve the LP minimize(- 4*x1 + 7* x2,consts,NONNEGATIVE); # get the basis (non zero variables) and then get the optimum dictionary solve(dic,{x1,x3,x4,z}); # find a gomory cut from the equation in the dictionary for x1 # update the consts and dic - x6 is the new slack variable consts:=consts union { x6 = -1/2 + 3*x2/4 + x5/4}; dic:= consts union obj; # end one iteration of Gomory's algorithm # start next iteration # solve the LP minimize( -4*x1 + 7*x2,consts,NONNEGATIVE); # get the basis (non zero variables) and then get the optimum dictionary # all variables are integer - we are done! # optimum objective function has value -8 quit;