Lazy constraint doesn't seem to work?

Specific Domains Optimization (Mathematical)
1

Here is my call_back function,it mainly used to elimilate sub-circle in route

	function call_back(cb_data)
		status = callback_node_status(cb_data, model)
		x_val = callback_value.(cb_data, model[:x])
		for i ∈ 1:m
			disconnected_parts = get_disconnected_parts(x_val[i, :, :])
			if length(disconnected_parts) <= 1
				continue
			end
			for disconnected_part in disconnected_parts
				println("Found cycle length: $(length(disconnected_part))")
				for cycle in [disconnected_part, reverse(disconnected_part)]
					S = [(cycle[end], cycle[1])]
					for i ∈ 2:length(cycle)
						push!(S, (cycle[i-1], cycle[i]))
					end
					println("Adding constraints: ", S)

					con = @build_constraint(sum(model[:x][i, j, k] for (j, k) in S) <= length(cycle) - 1)
					MOI.submit(model, MOI.LazyConstraint(cb_data), con)
				end
			end
		end
	end

When i solve the problem, it truely recognize the circle and add to constraint with information

Found cycle length: 4
Adding constraints: [(1, 4), (4, 3), (3, 2), (2, 1)]
Adding constraints: [(4, 1), (1, 2), (2, 3), (3, 4)]
Found cycle length: 4
Adding constraints: [(10, 11), (11, 9), (9, 12), (12, 10)]
Adding constraints: [(11, 10), (10, 12), (12, 9), (9, 11)]

But when i extract the route,the answer is

2-element Vector{Vector{Tuple{Int64, Int64}}}:
 [(2, 1), (4, 2), (1, 3), (3, 4), (11, 9), (9, 10), (12, 11), (10, 12)]
 [(5, 1), (8, 5), (1, 6), (6, 7), (7, 8)]

which is still contain the sub-circle, can someone point out where i am missing out?

2

I don’t immediately spot the problem, but it’s hard to tell without a reproducible example.

If you’re trying to solve a TSP, see this tutorial in the JuMP docs: Traveling Salesperson Problem · JuMP

1 Like