Skip to main content
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 ...
Philipp Christophel's user avatar
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 ...
Michael Trick's user avatar
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 ...
prubin's user avatar
  • 39.3k
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 ...
prubin's user avatar
  • 39.3k
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 ...
prubin's user avatar
  • 39.3k
6 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 ...
Kuifje's user avatar
  • 13.5k
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.
Erwin Kalvelagen's user avatar
6 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)....
prubin's user avatar
  • 39.3k
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 ...
prubin's user avatar
  • 39.3k
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 ...
worldsmithhelper's user avatar
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
Philipp Christophel's user avatar
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 ...
Alberto Santini's user avatar
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 \...
ErlingMOSEK's user avatar
  • 3,166
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 $\...
prubin's user avatar
  • 39.3k
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$), ...
prubin's user avatar
  • 39.3k
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 ...
prubin's user avatar
  • 39.3k
1 vote
Accepted

Sign of the reduced cost in LP

The reduced cost of a nonbasic variable $x$ is the net rate of change to the objective if you increase the value of $x$ by a small amount and optimally adjust the other variables to preserve ...
prubin's user avatar
  • 39.3k
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 ...
A.Omidi's user avatar
  • 8,950
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$ ...
Steven01123581321's user avatar
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 ...
Sutanu Majumdar's user avatar
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. ...
BehrouzB's user avatar
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 ...
naveen divakaran's user avatar

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