# Tag Info

Accepted

### Good references for reduced cost fixing?

Unfortunately, I can't provide you with a perfect reference or a textbook including examples but I can point you to a trail of papers/surveys pointing out the origin of reduced cost fixing. One survey ...
• 3,188
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,372

### 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 ...
• 39.1k
Accepted

### Can we have all reduced costs (strictly) positive?

This may depend on how you define "reduced costs". If you mean reduced costs as computed by the simplex algorithm, then no, it is not possible that all are strictly positive due to the mechanics of ...
• 39.1k

### Minimizing cost of transportation and storage of items

I would approach this as a mixed integer linear programming (MILP) problem. There are a number of MILP solvers, some open source, some commercial (with some of the commercial solvers providing free ...
• 39.1k
Accepted

### Interpretation of Reduced Costs

The reduced costs (or marginal costs), tell you by how much the objective function will increase (or decrease), if the corresponding variable increases by one unit. So if you are minimizing, the ...
• 13.3k

### What is the relation between dual variables and reduced costs?

If you interpret $$A= \begin{pmatrix}G \\ H\end{pmatrix}$$ then $$\pi^TA_j = \mu^T G_j + \lambda^T H_j$$ (where $\pi,\mu,\lambda$ are the corresponding duals) is not a surprise.
• 2,676
Accepted

### What is the relation between dual variables and reduced costs?

First, as a note, your formulation (minimizing with $\le$ constraints) will produce nonpositive shadow prices. It might be easier to understand if you use $\ge$ constraints (nonnegative shadow prices)....
• 39.1k

### Must the Newly Generated Column be used in RMP in the Column Generation Method?

I assume that you are minimizing. If you only add one column at a time, the new column should immediately enter the basis. If you add multiple columns with negative reduced costs before doing more ...
• 39.1k
Accepted

### Minimizing cost of transportation and storage of items

I won't write a python solution as i am not familiar with any python modeling language but i can describe the approach i took in the past to solve problems like this. I would solve this problem using ...
• 4,007
Accepted

### Can one strengthen the Lagrangian dual bound in column generation when there are multiple subproblems?

Yes, that bound is valid, and you can prove it by exhibiting a dual feasible solution with that objective value. I don’t have my copy handy, but Wolsey’s Integer Programming shows this. In fact, the ...
• 32k

### Negative reduced cost for basic variable

My guess would be that the variable is not basic, it is non-basic but at the upper bound of 1.0. Modern solvers use the generalized simplex method which allows for lower and upper bounds on a ...
• 3,188
Accepted

### When using column generation, can I delete a node with negative reduced cost from my subproblem?

If your sub-problem is a shortest path problem on a complete graph, without resource constraints, you can delete vertices which don't decrease the reduced cost. Indeed, for any path containing such a ...
• 2,113
Accepted

### Reduced cost fixing for binary programs

Assume you want to solve $$\begin{array}{ll} min & c^T x \\ st & A x = b \\ & x \geq 0 \end{array}$$ For any dual feasible solution $(\hat y,\hat s)$ it holds  \hat s = c - A^T \...
• 3,166

• 3,491
1 vote

### Minimizing cost of transportation and storage of items

Depending on what your decision variables are you are looking at an integer, mixed integer, or mixed integer linear programming problem. It seems to me that you want to solve it using a Python model. ...
• 51
1 vote
Accepted

### Preemptive Goal programming by fixing nonbasic variables with non-zero reduced costs

I think I have answered my own question over the last day. I found that fixing non-basic variable with non-zero reduced was enough to keep the optimal value of higher priority goals. The reason I was ...

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