3 ms·
Small point: If you want to do Monte Carlo on an LP (linear program), then using the simplex algorithm, for the first Monte Carlo trial, go ahead and find the
by graycat 3y ago
Small point: If you want to do Monte Carlo on an LP (linear program), then using the simplex algorithm, for the first Monte Carlo trial, go ahead and find the optimal solution. Then for the rest of the trials, start with the optimal solution, the basic variables, and the matrix inverse of the basis matrix and from those find the next optimal solution -- that solution will nearly always come quite quickly. So, you will be able to have a good collection of Monte Carlo trials for surprisingly little more computing than for the first optimal solution.
- taeric 3y agoI knew you can carry forward solutions in most solvers. I'd assume you would be changing constraints some, though I imagine most constraints would not be changed such that a lot of the discovered solution would still be good?
- graycat 3y agoThe change that would make finding the next solution maybe not quickly would be to the basis matrix and its inverse from the last solution. Still, finding a new basis inverse would be much faster than starting from just the whole problem. Yes, changes in the basis matrix could make that basis infeasible, but could attack that the usual way with artificial variables, and there may be still better ways. Changes in the costs c, the right hand side b, or the non-basic columns of matrix A would let the new solution be found usually quickly.