lp_solve is a free (see LGPL for the GNU lesser general public license)
linear (integer) programming solver based on the revised simplex method
and the Branch-and-bound method for the integers.