I was wondering if, given a min cost flow problem and an integer n, there is an efficient algorithm/package or mathematical method, to obtain the set of the n-best basic solutions of the min cost flow problem (instead of just the best).
How can I order the basic solutions of a min cost flow problem according to their cost?
71 Views Asked by Giacomo At
1
There are 1 best solutions below
Related Questions in OPTIMIZATION
- Optimize LCP ReactJs
- Efficiently processing many small elements of a collection concurrently in Java
- How to convert the size of the HTML document from 68 Kb to the average of 33 Kb?
- Optimizing Memory-Bound Loop with Indirect Prefetching
- Google or-tools soft constraint issue
- How to find function G(x), and make for every x, G(x) always returns fixed point for another function F(G(x))
- Trying to sort a set of words with the information theory to solve Worlde in Python but my program is way to slow
- Do conditional checks cause bottlenecks in Javascript?
- Hourly and annual optimization problem over matrix
- Sending asynchronous requests without a pre-defined task list
- DBT - Using SELECT * in the staging layer
- Using `static` on a AVX2 counter function increases performance ~10x in MT environment without any change in Compiler optimizations
- Is this a GCC optimiser bug or a feature?
- Performance difference between two JavaScript code snippets for comparing arrays of strings
- Distribute a list of positive numbers into a desired number of sets, aiming to have sums as close as possible between them
Related Questions in LINEAR-PROGRAMMING
- Error in running a multi-level mixed effects model on microbiome data
- Distribute a list of positive numbers into a desired number of sets, aiming to have sums as close as possible between them
- Linearlization of quadratic constraint
- Linear program solver CBC seems to give 'optimal' solutions with different objective for the exact same problem (and code)
- PYOMO: LP Heat storage optimalization problem, I want to define the domain of a variable with discrete floats
- How to interpret shadow price array shape in Gekko
- Simultaneous Spacing and Duration Constraints with time gaps in Gekko
- Time-based spacing constraints in Gekko
- Dealing with Non-Optimal Solutions from Gekko
- How to use layered conditional constraints in Gekko
- How to enforce specific elements in a vector to be in an optimization solution in Gekko
- How to write solution file for an LP problem with Coin-or Cbc Solver?
- Randomized Relaxation of Complex Linear Assignment Problem
- ortools solvers GLOP, PDLP instantly writes that the model is infeasible
- Binary and Integer Program in Python
Related Questions in INTEGER-PROGRAMMING
- About MATLAB intlinprog
- Binary and Integer Program in Python
- Use min/max operator inside integer linear programming constraint
- Stuck formulating an adjacency constraint with pyomo
- Formulating a constraint with pyomo
- Does the Order of Modeling Affect Computational Speed in Pulp for Integer Programming Problems?
- Gekko not solving Integer Programming Problem
- Mibs exception FileNotFoundError: [Errno 2] No such file or directory: 'mibs.mps'
- PAO.Pyomo model sets two variables x and y to be unique
- How to implement non-zero count constraint for cvxpy in integer programming
- Keeping count of variable occurence in google OR Tools
- Order elements in a matrix based on another matrix
- How to convert the following if-else conditions to Linear integer programming constraints?
- How to define this complex labor rule as a constraint in MIP?
- setting a lower bound constraint based on condition in gekko
Related Questions in SIMPLEX-ALGORITHM
- Libreoffice Solver to java implementation with apache-commons-math
- linear programming in R | limits to what it can do, or my mistake?
- CPLEX (or other open source LP solver) with access to simplex tableau (matrix) each iteration?
- Solve a linear programming (LP) problem in R
- compute the tableau's nonbasic term in SCIP separator
- custom cutter has invalid Lhs or Rhs
- How can I order the basic solutions of a min cost flow problem according to their cost?
- Example for SimplexSolver in Apache Commons Maths 3.6.1
- 2D fiber alignment using the simplex algorithm
- python network simplex algorithm for transportation problem?
- python networkX network simplex
- Revised simplex method enters endless loop
- How to create a simplex algorithm table
- How to write Simplex method (in tableau/matrix form) from scratch in python?
- Dual values of optimal bases
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Not so easy. There were some special LP solvers that could do that (see: Ralph E. Steuer, Multiple Criteria Optimization: Theory, Computation, and Application, Wiley, 1986), but currently available LP solvers can't.
There is a way to encode a basis using binary variables:
Using this, we can use "no good cuts" or "solution pool" technology to get the k best bases. See: https://yetanothermathprogrammingconsultant.blogspot.com/2016/01/finding-all-optimal-lp-solutions.html. Note that not all solution-pools can do the k-best. (Cplex can't, Gurobi can.) The "no-good" cuts work with any mip solver.
Update: a more recent reference is Craig A. Piercy, Ralph E. Steuer, Reducing wall-clock time for the computation of all efficient extreme points in multiple objective linear programming, European Journal of Operational Research, 2019, https://doi.org/10.1016/j.ejor.2019.02.042