Efficient way to restrict the domain of variables?

Specific Domains Optimization (Mathematical)
,
1

Which one is more efficient in term of computational time? (I’m looking forward to read a general answer, but below is a simple example to describe the situation)

Suppose you have a large network (over 1K nodes and 10K edges). If we want to create a varibles such as x[i,j,p] representing a person’s connections (their nodes that create edges); is it better to do (1) or (2) ?

y_sets = [(i,r,d) for d in drivers for r in riders for i in Acc_rd[r,d]]

# 1  defining very general and then in constraints imposing/checking a condition#

using Graphs, SimpleWeightedGraphs

g = SimpleWeightedGraph(start_node, end_node, W)   # W are strength of connections

m = Model();
N = 1:25
P = 1:10


@variable(m, x[N,N, P] >= 0, Bin);    #This way,  in term of conncetions, some of the combinations are invalid

@constraint(m, [i in N, p in P], sum(x[i,j,p] for j in N, p in P)  >= 1 if has_edge(g, i, j))

# 2 defining via imposing conditions

using Graphs, SimpleWeightedGraphs

g = SimpleWeightedGraph(start_node, end_node, W)   # W are strength of connections

m = Model();
N = 1:25
P = 1:10

x_conditioned = [(i,j,p) for i in N for j in N  for p in P  if has_edge(g, i, j)]
@variable(model, x[x_conditioned]>= 0, Bin) 


@constraint(m, [i in N, p in P], sum(x[i,j,p] for j in N, p in P) >= 1)

I was wondering if we put limits on for array indexing of a variable x is efficientor it makes no difference. Because having used tuples for array indexing makes writing constraint difficult

2

Most solvers (particularly MILP) have a presolve which will remove unused variables. So option 2 might be a little faster (it’s creating less variables at the JuMP end), but shouldn’t affect the solve very much.

I’d try both options and see what the difference is.

1 Like