9
votes
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,168
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 ...
- 2,362
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 ...
- 37.8k
8
votes
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 ...
- 37.8k
6
votes
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 ...
- 37.8k
6
votes
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,585
5
votes
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 ...
- 37.8k
5
votes
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)....
- 37.8k
5
votes
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 ...
- 3,975
5
votes
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 ...
- 12.9k
4
votes
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 ...
- 30.4k
4
votes
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,168
4
votes
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,073
2
votes
Dual of a model to obtain reduced costs
It's a bit tricky to sort out what is going on here. Given a dual solution ($\lambda,\gamma,\theta$) to the LP relaxation of the master problem, your subproblem will need to solve for $a_{ir}$ and $\...
- 37.8k
2
votes
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,046
2
votes
How to calculate EOQ in this problem?
You are correct about the demand and setup cost. The presence of "Value" in the numerator of the EOQ formula is an error. $K$ is the order setup cost (which is why you have seen it as $S$), ...
- 37.8k
1
vote
Accepted
The dual values and change in the variables values
Let $\bar{A}$ and $\bar{x}$ be $A$ and $x$ augmented by slack variables, so that the constraints become $\bar{A} \bar{x} = b.$ The LP solution partitions $\bar{A} = [B N]$ (after permuting columns if ...
- 37.8k
1
vote
Accepted
Understanding reduced costs and dual values
One of the best possible ways for the models with some difficulties to understand how the model can be treating in the solving process, specifically in the situations like infeasibility, comparing ...
- 8,390
1
vote
Accepted
How to calculate EOQ in this problem?
I find the wordings pretty confusing, but the way I see it:
for (a)
If binding & printing both happen, then for every ordered batch, you incur the costs $7500 + 1500 = 9000$. So ordering $10$ ...
- 1,043
1
vote
How to obtain reduced cost in the graphical sensitivity analysis?
As I understand suppose $z= 6x+2y-1$ then max of z would be at
$x,y=(6,0)$ for x bounded by $[0,6]$ and $y=[0,3]$. Imagine z is the negative sloping line or contour in x-y plane.
Slope of contour z is ...
- 3,343
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 ...
- 113
Only top scored, non community-wiki answers of a minimum length are eligible