title: iteratively finding the best k solutions to linear/binary programming problems
body: <p>I am solving a maximization binary programming problem (binary programming is the same as integer programming but the solution is a vector of 0's and 1's). I would like to find the best 10 solutions. I don't mean the best 10 solutions where all 10 objective function values are necessarily equal -- but rather: i want the first solution to be the optimal solution with the given constraints; i want the second solution to be optimal, if the first solution is ruled out; the third solution must be optimal if the first and second solution are ruled out, and so on.</p>
  
  <p>I am using the lpSolve package in R, which gives only the single best solution. so i have written a script which attempts to iteratively find the best k solutions as follows: </p>
  
  <pre><code>for (j going from 1 to k){
    (1) given the set of constraints, find the best solution, and record it
    (2) add a new constraint (such that the solution found in (1) is invalid) to the set of constraints
  }
  </code></pre>
  
  <p>my script repeats <code>(1)</code> and <code>(2)</code> k times and reports the k solutions as well as the value of the objective function for each of the k solutions.</p>
  
  <p>Now, here is my problem: 
  by my understanding, for a maximization problem, the j-th solution must always have an objective value that is less than or equal to the (j-1)-th solution (right?), that is the objective values must be monotonically decreasing because the j-th solution and the (j-1)-th solution satisfy all the same constraints, except that the j-th solution must satisfy one additional constraint that the (j-1)-th solution does not necessarily satisfy.</p>
  
  <p>however, this is not the case with my script. there is definitely a downward trend but the objective values are NOT monotonically decreasing. below is a graph of  objective values vs. k: </p>
  
  <p><a href="https://i.stack.imgur.com/tX1wd.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/tX1wd.png" alt="enter image description here"></a></p>
  
  <p>I would like to know: is the problem with lpSolve? is there a problem with my script? should the objective function values even be monotonically decreasing or is my understanding skewed? </p>
  
  <p>UPDATE: i managed to replicate the described procedure in the other lpSolve interface for R, lpSolveAPI and got a monotonically decreasing graph as expected. so i think lpSolve is problematic. </p>