Brief Description:
This discussion focuses on optimizing two subway lines to cover stations independently, but the model’s “unique_father_only” constraints are unintentionally forcing both lines to cover all stations, even without active “station_connectivity” constraints. Ideally, the solver should allow each line to form independent paths, or even leave links inactive, if “station_connectivity” is disabled.
Model Objective Summary
This model is designed to create two distinct subway lines that minimize the total length of active links between subway stations, under certain structural constraints. Each line should ideally form an independent or partially overlapping path, connecting stations in a way that maintains a clear starting and ending point, with limited branching and adherence to specific connectivity requirements.
Problem Details:
In my model, I aim to create two separate subway lines (using sets L1 and L2) that do not necessarily need to cover all stations in set S. The goal is for the lines to form independent or partially overlapping paths. I included a “unique_father_only” constraint for each line to ensure that each line has at most one start and one end. However, despite disabling the “station_connectivity” constraint, both lines end up covering all stations, which is not intended. The solver should ideally leave some links inactive if station connectivity isn’t required.
Additionally, I used an auxiliary set, A, with the same indices as S to implement the “unique_father_only” constraints. Initially, attempts to implement these constraints directly on S encountered issues, especially with links lacking the necessary s=1 in the network data.
Questions:
- How can I prevent the “unique_father_only” constraints from implicitly forcing all stations to be covered?
- Are there alternative ways to handle the auxiliary set
Ato simplify the constraints?
Any insights on structuring these constraints or adjustments to achieve the intended partial coverage on both lines would be greatly appreciated. Thank you!
.mod code
# Subway Line Optimization Model - Version 1.2
# Supports two distinct subway lines (L1 and L2)
# ------------------- Sets -------------------
set S within {0..4000}; # Set of subway stations
set A := S; # Auxiliary set for stations
# Define subway line segments for Line 1 and Line 2
set L1 within {0..4000} cross S cross S; # Line 1 segments (unique paths)
set L2 within {0..4000} cross S cross S; # Line 2 segments (unique paths)
# ------------------- Parameters -------------------
# Station parameters: coordinates on a Cartesian plane
param X {S}; # X coordinate of station
param Y {S}; # Y coordinate of station
# Segment length parameters for each line
param length_1 {L1}; # Length of each segment in Line 1
param length_2 {L2}; # Length of each segment in Line 2
# ------------------- Variables -------------------
# Line connection indicators for Line 1
var beta_rs_1 {L1} binary; # 1 if station s is the "son" of station r on Line 1
var beta_sr_1 {L1} binary; # 1 if station r is the "son" of station s on Line 1
var alpha_1 {L1} binary; # 1 if the link between r and s on Line 1 is active
# Line connection indicators for Line 2
var beta_rs_2 {L2} binary; # 1 if station s is the "son" of station r on Line 2
var beta_sr_2 {L2} binary; # 1 if station r is the "son" of station s on Line 2
var alpha_2 {L2} binary; # 1 if the link between r and s on Line 2 is active
# Station relationship variables for both lines
var sons_1 {A} binary; # 1 if the station has "sons" on Line 1
var fathers_1 {A} binary; # 1 if the station has "fathers" on Line 1
var unique_1 {A} >= 0; # Absolute value of (fathers_1[a] - 1) for Line 1
var sons_2 {A} binary; # 1 if the station has "sons" on Line 2
var fathers_2 {A} binary; # 1 if the station has "fathers" on Line 2
var unique_2 {A} >= 0; # Absolute value of (fathers_2[a] - 1) for Line 2
# ------------------- Objective Function -------------------
# Objective: Minimize the total length of active links in both lines
minimize routes:
sum {(l1,r,s) in L1} (alpha_1[l1,r,s] * length_1[l1,r,s])
+ sum {(l2,r,s) in L2} (alpha_2[l2,r,s] * length_2[l2,r,s]);
# ------------------- Constraints -------------------
# 1. Station Connectivity: Ensure every station is connected to at least one other station on either line
subject to station_connectivity {a in A}:
sum {(l1,r,s) in L1 : r = a} alpha_1[l1,r,s]
+ sum {(l1,r,s) in L1 : s = a} alpha_1[l1,r,s]
+ sum {(l2,r,s) in L2 : r = a} alpha_2[l2,r,s]
+ sum {(l2,r,s) in L2 : s = a} alpha_2[l2,r,s] >= 1;
# 2. No Splitting of Lines: Limit each station to at most 2 active connections (1 incoming and 1 outgoing) for each line
subject to splitting_rule_L1 {a in A}:
sum {(l1,r,s) in L1 : r = a} alpha_1[l1,r,s]
+ sum {(l1,r,s) in L1 : s = a} alpha_1[l1,r,s] <= 2;
subject to splitting_rule_L2 {a in A}:
sum {(l2,r,s) in L2 : r = a} alpha_2[l2,r,s]
+ sum {(l2,r,s) in L2 : s = a} alpha_2[l2,r,s] <= 2;
# 3. Spanning Tree Structure: Ensure each link has only one direction as "father-son"
subject to spanning_tree_1 {(l1,r,s) in L1}:
beta_rs_1[l1,r,s] + beta_sr_1[l1,r,s] = alpha_1[l1,r,s];
subject to spanning_tree_2 {(l2,r,s) in L2}:
beta_rs_2[l2,r,s] + beta_sr_2[l2,r,s] = alpha_2[l2,r,s];
# 4. Son Count Constraints: Count the number of sons each station has for each line
subject to count_sons_1 {a in A}:
sum {(l1,r,s) in L1 : s = a} beta_rs_1[l1,r,s]
+ sum {(l1,r,s) in L1 : r = a} beta_sr_1[l1,r,s] = sons_1[a];
subject to count_sons_2 {a in A}:
sum {(l2,r,s) in L2 : s = a} beta_rs_2[l2,r,s]
+ sum {(l2,r,s) in L2 : r = a} beta_sr_2[l2,r,s] = sons_2[a];
# 5. Father Count Constraints: Count the number of fathers each station has for each line
subject to count_fathers_1 {a in A}:
sum {(l1,r,s) in L1 : r = a} beta_rs_1[l1,r,s]
+ sum {(l1,r,s) in L1 : s = a} beta_sr_1[l1,r,s] = fathers_1[a];
subject to count_fathers_2 {a in A}:
sum {(l2,r,s) in L2 : r = a} beta_rs_2[l2,r,s]
+ sum {(l2,r,s) in L2 : s = a} beta_sr_2[l2,r,s] = fathers_2[a];
# 6. Define "unique" as the absolute value of (fathers[a] - 1) for each line
subject to absolute_value_pos_1 {a in A}:
unique_1[a] + 1 >= fathers_1[a];
subject to absolute_value_neg_1 {a in A}:
-1 * unique_1[a] + 1 <= fathers_1[a];
subject to absolute_value_pos_2 {a in A}:
unique_2[a] + 1 >= fathers_2[a];
subject to absolute_value_neg_2 {a in A}:
-1 * unique_2[a] + 1 <= fathers_2[a];
# 7. Ensure Each Line Has At Most One Starting and One Ending Station
subject to unique_father_only_1:
sum {a in A} (1 - sons_1[a] + unique_1[a]) <= 2;
subject to unique_father_only_2:
sum {a in A} (1 - sons_2[a] + unique_2[a]) <= 2;
# End of Model
.dat code “Lines info”
#--------------Line links configuration----------------
# Links parameters
set L1:=
# l r s
1 1 2
2 1 3
3 1 4
4 1 5
5 1 6
6 2 3
7 2 4
8 2 5
9 2 6
10 3 4
11 3 5
12 3 6
13 4 5
14 4 6
15 5 6
;
set L2:=
# l r s
1 1 2
2 1 3
3 1 4
4 1 5
5 1 6
6 2 3
7 2 4
8 2 5
9 2 6
10 3 4
11 3 5
12 3 6
13 4 5
14 4 6
15 5 6
;
P.S. I’m new to modeling, AMPL, and CPLEX, so any tips or recommendations for improving my approach are greatly appreciated. I’m eager to learn best practices and efficient ways to structure constraints or simplify my model, so any insights would be helpful. Thank you! 