Questions tagged [reduced-costs]

The tag has no usage guidance.

7 questions
Filter by
Sorted by
Tagged with
2answers
331 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 "...
1answer
488 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$) : ...
1answer
115 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 } \...
1answer
110 views

Dual of a model to obtain reduced costs

I have the following model which I am going to solve with column generation. Basically it is a VRP problem with pick-up and delivery in which couriers are assigned to a set of shifts based on their ...
1answer
110 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 ...
0answers
57 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 ...
0answers
86 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 ...