We provide simple R-functions to approximately (but efficiently) solve many large binary integer programs (BILPs), including 0-1 multidimensional knapsack problems, which are a stretch even for large-scale linear solvers. We follow the primal-dual approach of D. P. Williamson: LP relaxation of the primal BILP, solution of the dual LP, complementary slackness to assign primal binaries, and comparison of resulting objective function value to the relaxed dual LP bound to gauge precision. More specifically, we approximately solve a collapsed version of the dual LP using a simple nonlinear solver (nlminb) followed by a simple shadow price sort to assign primal binaries.
Although this approach is not guaranteed to surpass other heuristics, and in some cases it is clearly inferior, for many large problems the resulting binary solution value is very close to the relaxed dual bound. Using this approach, we were able to approximately solve a maximization BILP with 300 constraints and 50,000 variables in about 57 minutes on a beefy Dell XPS Tower PC. The resulting BILP value was within 99.9% of the dual upper bound. Results for a minimization BILP were similar.
This repository has been overhauled as of April 2026. We have sharpened the collapsed nonlinear dual solver with specified gradients and tightened control parameters. We have also added IP and LP solvers from R-library lpSolve for comparison on small to moderately sized problems. We have also added a variety of example problems from J. E. Beasley’s OR-Library (people.brunel.ac.uk/~mastjjb/jeb/info.html). Finally, we have cleaned up our R-functions to provide clear, consistent outputs.
Although we include small example problems where an exact optimal BILP solution is readily available, we obviously don’t recommend approximation in such cases. Our approximate BILP approach is reserved for larger problems where exact solutions, or better approximations, are either laborious or totally unavailable.
One other addition is Python code and results for some of the example problems with initial reference to codeconvert.ai/r-to-python-converter. In particular, our very large problem produced the same results on the same data, but much faster in Python - in only about 7 minutes! We used a small solver step size in R, but that probably doesn’t fully account for the speed difference. Some of the array mechanics in Python NumPy must be considerably more efficient than comparables in R.