Gurobi 9.0.0 // C++ // LP
Let us assume the following problem with three nodes:
node (1) is producing something and it gets transported to the demand at
node (2) and
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_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)