# 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 something and it gets transported to the demand at node (2) and node (3).

Now I do have the option to build either new factories or roads.

I created the variables 0 <= build_factory <= 1 and 0 <= build_road <= 1. All relevant constraints of the new objects are multiplied with build_factory and build_road respectively. The investment cost in the objective function are also multiplied with these variables.

Mathematical formulation of the problem as an example. The problem shows the decision of increasing the production facility at node (1)

All variables >= 0

Initial Problem (LP): x1 factory, x2 and x3 demand

max - 0.5x1 + 1.5x2 + 1.5x3
s.t. x1 - x2 -x3  = 0 (Supply=Demand)
x1          <= 3 (Capacity Road 1, (1)-(2), (redundant))
x1 - x2     <= 1 (Capacity Road 2, (2)-(3))
x1          <= 2 (Production Capacity node 1)
x2          <= 2 (Demand Capacity node 2)
x3          <= 1 (Demand Capacity node 3)


Optimal solution = 2 with x1 = 2 and either x2 = 2 or x2 = x3 = 1

The demand is not exhausted and there is room for improvement.

Build option added (LP -> MILP) through binary variable y4 representing building an additional factory with capacity x4 at node (1):

max - 0.5x1 + 1.5x2 + 1.5x3 - 0.5x4 - 0.25y4
s.t. x1 - x2 -x3 + x4        = 0 (Supply=Demand)
x1          + x4       <= 3 (Capacity Road 1, (1)-(2))
x1 - x2     + x4       <= 1 (Capacity Road 2, (2)-(3))
x1                     <= 2 (Production Capacity node 1)
x2                     <= 2 (Demand Capacity node 2)
x3                     <= 1 (Demand Capacity node 3)
x4       <= 2 (Production Capacity also node 1)
x4 -2*y4 <= 0 (Restriction to only use when built)
y4  e [0,1] (Build variable)


For a MILP the optimal solution = 2.75 with x4 = y4 = 1. If I relax the MILP the optimal solution = 2.875 with x4 = 1 and y4 = 0.5. So building the production facility makes sense but it would be better to build a smaller one.

Now imagine there was another factory or road that could be built alternatively and has build variable y5. In the optimal solution of the MILP I might get y4 = 1 and y5 = 1 and even if one of them is smaller than 1 in the relaxed problem, I still can't determine which is the better option or am I mistaken? I calculate the dual price in case of y4 = 1 and y5 = 1 but can I be sure that the one with the heigher dual price is the better option considering building the whole object?

The main question is: How can I determine which is the better project?

I identified three problems regarding that question:

Problem 1: Is it possible to compare expansion possibilities by comparing the corresponding build variables in the relaxed model (and maybe use the dual price as an additional criterium)?

Problem 2: Now this still leads to the problem of interdependencies of the "build"-objects.

In the example above it could be the case that a new factory at node (1) is only useful in combination with an increase in road capacity from node (1) to node (2). However, I might not be able to build all suggested objects. How can I avoid these interdependencies?

Problem 3: Additionally, I do not know what the optimal factory or road capacity is in case of build_x = 1 in the the relaxed model. I only know that the suggested object should be built completely. Due to the size of the original problem, the creation of variables and constraints for multiple different sized factories or roads is not feasible. How can I find the optimal size for new objects?

If you have any suggestions on how I can mitigate/solve these problems, it would help me a lot.

Note: Running the whole thing as an MILP once is not feasible due to size of the problem (execution time) and the iterative process I currently use to avoid too strong interdependencies. Therefore I only solve the relaxed model in every iteration.

(Gurobi reduced cost = shadow price = dual price)

• Welcome to OR.SE. It would be great if you could produce an initial mathematical formulation on your problem. (e.g. LP/MIP/...) and if you will need to do a sensitivity analysis in your problem, it can be helpful. – A.Omidi Sep 22 at 5:17
• @A.Omidi thanks for the hint. I added a mathematical formulation of the example to clarify the problem. A sensitivity analysis in terms of dual price is done if the build variable is 1 in the relaxed model. I added this point also. – Mitch Sep 22 at 13:46