# Tag Info

## New answers tagged linear-programming

### 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
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. ...
• 3,898

### 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
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
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,924

### 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
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 ...
• 2,342

### 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
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

### 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....
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
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
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
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
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 ...
• 1,700