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 ...
  • 31.9k
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 ...
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: "...
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 ...
  • 236
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.1k
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 ...
  • 31.9k
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 ...
  • 31.9k
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.1k
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
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 ...
  • 31.9k
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.
  • 31.9k
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 ...
2 votes
Accepted

Multi-objective optimization for resource allocation

This is not necessarily a multiobjective problem. One approach is to write a single linear program (if allocation amounts are continuous) or mixed integer linear program (if allocation amounts are ...
  • 31.9k

Only top scored, non community-wiki answers of a minimum length are eligible