Questions tagged [reduced-costs]
The reduced-costs tag has no usage guidance.
21
questions
1
vote
3
answers
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
2
votes
1
answer
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
1
answer
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 ...
2
votes
1
answer
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, ...
- 21
2
votes
1
answer
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 ...
- 66
4
votes
1
answer
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
2
votes
2
answers
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
8
votes
1
answer
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 ...
- 606
2
votes
1
answer
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
8
votes
1
answer
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 ...
- 81
1
vote
1
answer
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:
...
- 61
5
votes
1
answer
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
4
votes
2
answers
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 ...
- 421
5
votes
3
answers
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
6
votes
1
answer
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
3
votes
0
answers
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
0
answers
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
6
votes
1
answer
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
5
votes
1
answer
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 ...
- 113
7
votes
1
answer
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
10
votes
2
answers
1k
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 "...
- 359