New answers tagged

2 votes

Tutorial request on implementing HiGHS solver

On Python side, there are two alternatives beside scipy implementation. You can use PuLP dev version as explained in question How to call HiGHS solver from python PuLP MIP? There is also a Python ...
  • 256
5 votes
Accepted

Tutorial request on implementing HiGHS solver

To write and solve a problem in Julia, implement it using JuMP. I assume you already installed the JuMP and HiGHS package as both install like normal Julia packages. ...
2 votes

How do you recover dual variables for a minimum weight bipartite perfect matching problem?

If we assume that $y$ corresponds to the constraints $\sum_i x_{ij}=1$ and $z$ corresponds to the other set of constraints, then you have a $(2n)\times (2n)$ system of equations $$y_j + z_i = c_{ij}$$ ...
  • 32k
6 votes
Accepted

How to call HiGHS solver from python PuLP MIP?

PuLP has an API for HiGHS but that version is not sent to pip yet. For the time being, you should pip install PuLP from Github. See the command taken from their readme below. (ps. You might need to ...
  • 256
6 votes
Accepted

Finding a dual feasible basis for use with the dual simplex algorithm

First of all, off course there are dual phase 1 methods that find a dual feasible basis that is not necessarily primal feasible as a first step in a 2-phase dual simplex method. In Maros: "...
2 votes

Totally unimodular towards linear programming relaxation

Does a TUM matrix $A$ always have a square submatrix $B$ with determinant $\pm 1?$ Technically, no. A matrix entirely filled with zeroes is TUM but obviously has no nonsingular submatrices. In the ...
  • 32k
8 votes
Accepted

Inconsistent teachings on how to choose a non basic variable to enter the basis (primal simplex)

As long as you choose something with a negative reduced cost, the simplex algorithm "works". See https://people.orie.cornell.edu/dpw/orie6300/Lectures/lec13.pdf for examples of ways you can ...
8 votes

Column generation: decreasing value of restricted master problem

The reduced cost is the instantaneous rate of change as you increase the value of the new variable from 0. The actual impact of the new variable on the objective function is piecewise linear and ...
  • 32k
3 votes
Accepted

Convex not strictly convex!

I think you are confusing two things here. A linear program has a convex feasible region. The term "convex space" refers to an entire vector space, not to a particular region (such as an LP ...
  • 32k
4 votes

How to find the product with best specs at least price?

If someone told you that linear programming could be applied to this problem, it could be that they were thinking of Data Envelopment Analysis (DEA), - see Wikipedia. DEA assumes a linear utility, i.e....
4 votes
Accepted

How to find the product with best specs at least price?

If you are just choosing between two or more products, it has nothing to do with linear programming. You are looking for a utility function to rank the products. Typically, this presumes that (a) you ...
  • 32k
3 votes
Accepted

Flow problem with side constraints: how to eliminate subtours?

Let $S$ be the set of arcs in a subtour of size $4$. No-good cuts are simple but weak: $$\sum_{(i,j)\in S} x_{ij} \le 4 - 1$$ Depending on the objective, you might get by with instead imposing no-...
  • 23.3k
6 votes
Accepted

Non-Integral Optimal Solutions of Totally Unimodular Linear Programs

With presolver and crossover both disabled, the SAS interior point algorithm returns $x_{ij} = 1/n$ for the (TU) problem of sending one unit of flow from node $0$ to node $n+1$ in a directed network ...
  • 23.3k
2 votes
Accepted

Developing the dual model

Your first dual constraint is wrong. The term $(1-\lambda)\times y^1$ should be included in the left side of the second dual constraint.
  • 32k
2 votes
Accepted

How to enumerate all vertices of a polyhedron as a stream

You can check the lrs software implemented by David Avis from McGill. The software implements the reverse search algorithm described in this serie of papers: Reverse Search: Origins Since the output ...
3 votes

Are optimization results stochastic?

In Gurobi, there is a parameter called seed which "typically leads to different solution paths". But the default value is ...
  • 604

Top 50 recent answers are included