# Questions tagged [reduced-costs]

The tag has no usage guidance.

21 questions
Filter by
Sorted by
Tagged with
1 vote
73 views

### The dual values and change in the variables values

For a constraint as Ax <= b, the dual shows the change in the objective function if the RHS increases by 1 unit. Now my question is that how we can determine how the optimal values will change by 1 ...
• 400
125 views

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

Consider a Linear Programme (LP) \begin{align} \min && \sum_{i \in I} c_i x_i \\ \text{s.t.} && \sum_{i \in I} a_{ij} x_i &\geq b_j & \quad & \forall j \in J \\ && ...
1 vote
375 views

### Sign of the reduced cost in LP

I'm new to operation research. I'm confusing about the sign of reduced cost and I have a few questions that I'd like to ask. Suppose that I solve a maximization problem, considering a variable x with ...
134 views

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

When I used Column Generation, I found a column with reduced cost < 0, and added it to the Restricted Master Problem. Must the newly added column be used in the solution of RMP at once? If not, ...
146 views

### Reduced cost fixing for binary programs

Consider the binary program $$\min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$ where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
214 views

### Understanding reduced costs and dual values

I have a headache regarding calculating the reduced costs of a linear program. I am using Pulp for modelling and CBC for solving. What I do is, I model a linear programming problem based on a rhs ...
• 1,133
163 views

### How to calculate EOQ in this problem?

I am trying to solve a problem that requires I find the EOQ. This problem is from the book (translation from greek) Operational Research: Theory, Algorithms and Applications by authors Coletsos John &...
• 205
505 views

### Good references for reduced cost fixing?

Reduced cost fixing is a technique used by mixed integer programming (MIP) solvers to safely fix variables to certain values. While this technique is well-known among the MIP community, I don't know ...
286 views

### Inconsistent teachings on how to choose a non basic variable to enter the basis (primal simplex)

During the primal simplex algorithm, a non-basic variable must be chosen to enter the basis. Many resources on the subject choose a variable based solely on its coefficient in the row of the tableau ...
• 137
265 views

### Column generation: decreasing value of restricted master problem

I am using column generation to solve a minimization problem. At a given iteration, my subproblem finds a column with reduced cost $-1$, and in the following restricted master problem, this new column ...
1 vote
648 views

### How to obtain reduced cost in the graphical sensitivity analysis?

According to some tables in the book Operations Research by Hamdy Taha(7th edition), it seems that for a variable whose optimal value is zero, reduced cost can be evaluated by the following formulas: ...
5k views

### Interpretation of Reduced Costs

I am looking for an answer to a question I can't quite get behind. (continuation of Linear Programming: Integer and non-integer decision variables) I am given the following mathematical optimization ...
• 123
2k views

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

My background: Pure math current Undergrad, learned the theory of Operations Research, but pretty basic. All we covered have been dealing with problems that have only 1 constraint matrix. I have dealt ...
695 views

### Minimizing cost of transportation and storage of items

I am looking for an optimization algorithm to minimize the cost of transportation and storage cost in warehouse. Let's assume the following table gives us the weekly forecast of Demand. ...
• 205
397 views

### Dual of a model to obtain reduced costs

I have the following model which I am going to solve with column generation. \begin{align} \max & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s}\beta_{bs}p_r y_{br}\label{objective-set1}\\ ...
• 61
145 views

### Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?

I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
• 181
1 vote
148 views

### Expansion heuristic using gurobi reduced cost / shadow price (LP)

Gurobi 9.0.0 // C++ // LP Let us assume the following problem with three nodes: (1)-----(2)-----(3) node (1) is producing ...
• 93
201 views

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

I am solving a minimization problem with a column generation procedure. The master problem is of the form $$\min \sum_{i\in \Omega}c_i \lambda_i$$ subject to  \sum_{i\in \Omega \mid v \in i } \...
• 12.9k
156 views

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

I have been using the method of fixing nonbasic variables with non-zero reduced costs to do preemptive goal programming. It works for the most part. But I have recently noticed in a certain instance ...
1k views

### Negative reduced cost for basic variable

I am observing something unusual : after solving a linear program, some basic variables have negative reduced costs (instead of $0$) : ...
• 12.9k
I had a number of students claim on their homework that "All $z_j-c_j$ values are positive, therefore the solution is optimal." Of course, I noted that they should say "non-negative" instead of "...