Problem construction advice in JuMP for speed

Specific Domains Optimization (Mathematical)
,
1

I know that parallelization of problem construction has been advised against, so I am curious on what advice there is. Problem construction takes a significant amount of time on my problem, and is time significant operation.

What can I change about my problem set up to make this construct faster. Alternatively, is it possible to parallelize?
The loop that takes a lot of time is this runnable subset.

using JuMP
struct TransporterProblem
	durationLookUp
	numberOfStations 
	moveWhen
	followedByTime
	order
	moveCommandCount
end 
moveCommandCount = 28
numberReachableStations = 6
model = Model()
@variable(model, order[1:moveCommandCount, 1:moveCommandCount,1:numberReachableStations, 1:numberReachableStations ], Bin)	
@variable(model, moveWhen[1:moveCommandCount] >= 0.0 )
durationLookUp = rand(numberReachableStations, numberReachableStations)
followedByTime = rand(moveCommandCount)
transporterProblem = TransporterProblem(durationLookUp, numberReachableStations, moveWhen, followedByTime, order, moveCommandCount )
function moveDuration(moveIdx::Integer, transporterProblem::TransporterProblem)
	sum(
		sum(sum(transporterProblem.order[moveIdx,:, idxFrom,idxTo])* transporterProblem.durationLookUp[idxFrom, idxTo] 
			for idxFrom in 1:transporterProblem.numberOfStations
		) 
	for idxTo in 1:transporterProblem.numberOfStations
	)
end

function beginningOfOrderedOp(moveOrderIdx::Integer, transporterProblem::TransporterProblem)
	transporterProblem.moveWhen[moveOrderIdx]
end

foreach(1:moveCommandCount-1) do orderIdx
    println(orderIdx)
    spaceMove = 1.0
    @constraint(model, 
        beginningOfOrderedOp(orderIdx,transporterProblem)+
        sum( sum(order[moveIdx, orderIdx,:,:])*
        (moveDuration(moveIdx, transporterProblem) + transporterProblem.followedByTime[moveIdx])
        for moveIdx in 1:moveCommandCount) + spaceMove
            <= beginningOfOrderedOp(orderIdx+1,transporterProblem)
        )
end
1 Like
2

I found a way, really banging my head now.
If I look up on the right index my problem construction time really collapses.

using JuMP
struct TransporterProblem
	durationLookUp
	numberOfStations 
	moveWhen
	followedByTime
	order
	moveCommandCount
end 
moveCommandCount = 28
numberReachableStations = 6
model = Model()
@variable(model, order[1:moveCommandCount, 1:moveCommandCount,1:numberReachableStations, 1:numberReachableStations ], Bin)	
@variable(model, moveWhen[1:moveCommandCount] >= 0.0 )
durationLookUp = rand(numberReachableStations, numberReachableStations)
followedByTime = rand(moveCommandCount)
transporterProblem = TransporterProblem(durationLookUp, numberReachableStations, moveWhen, followedByTime, order, moveCommandCount )
function moveDurationOrderIdx(orderIdx::Integer, transporterProblem::TransporterProblem)
	sum(
		sum(sum(transporterProblem.order[:,orderIdx, idxFrom,idxTo])* transporterProblem.durationLookUp[idxFrom, idxTo] 
			for idxFrom in 1:transporterProblem.numberOfStations
		) 
	for idxTo in 1:transporterProblem.numberOfStations
	)
end

function beginningOfOrderedOp(moveOrderIdx::Integer, transporterProblem::TransporterProblem)
	transporterProblem.moveWhen[moveOrderIdx]
end

foreach(1:moveCommandCount-1) do orderIdx
    println(orderIdx)
        spaceMove = 1.0
        @constraint(model, 
        beginningOfOrderedOp(orderIdx,transporterProblem)+
        moveDurationOrderIdx(orderIdx, transporterProblem)+ 
        sum( sum(order[moveIdx, orderIdx,:,:])*
        (transporterProblem.followedByTime[moveIdx])
        for moveIdx in 1:moveCommandCount) + spaceMove
            <= beginningOfOrderedOp(orderIdx+1,transporterProblem)
        )
end
3

So this might be an issue related to column vs row based storage of arrays?

It looks like the model size (variables, constraints) are moderate. How long does the construction take?

4

The first way took something like 20 seconds, my solution took like a half second.

5

It looks like your first model is a quadratic program, whereas the second one is a linear program? That explains the difference in build speed.