Questions tagged [reduced-costs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
1 answer
453 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 ...
user avatar
  • 123
4 votes
2 answers
547 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 ...
user avatar
5 votes
3 answers
417 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. ...
user avatar
  • 205
6 votes
1 answer
293 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}\\ ...
user avatar
3 votes
0 answers
87 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 ...
user avatar
1 vote
0 answers
104 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 ...
user avatar
  • 83
6 votes
1 answer
129 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 } \...
user avatar
  • 10.1k
5 votes
1 answer
127 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 ...
user avatar
7 votes
1 answer
697 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$) : ...
user avatar
  • 10.1k
10 votes
2 answers
757 views

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 "...
user avatar
  • 349