Questions tagged [reduced-costs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer

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 ...
  • 65
8 votes
1 answer

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
0 answers

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: ...
  • 111
5 votes
1 answer

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
4 votes
2 answers

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 ...
5 votes
3 answers

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
6 votes
1 answer

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}\\ ...
3 votes
0 answers

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 ...
1 vote
0 answers

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 ...
  • 83
6 votes
1 answer

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 } \...
  • 10.9k
5 votes
1 answer

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 ...
7 votes
1 answer

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$) : ...
  • 10.9k
10 votes
2 answers

Can we have all reduced costs (strictly) positive?

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 "...
  • 359