Hinting a known feasible solution to a MILP solver with Google OrTools mathopt in Python

[Sacropyne]

Hi,

I have been going through the online documentation and the samples available on Github, but I was not able to find an example on how to provide an initial solution (or warm start, or solution hint, depending on the preferred synonym) to a compatible MILP solver when modelling through OrTools mathopt in Python.

Would you have a simple example available for this ?

Note if that helps that I am working with OrTools version 9.10.

Thanks a lot !

(I tried going through both the documentation and the source code, I found the SolutionHint class but I don’t know how to use it)

PS : not being sure of the preferred channel for such a question I also posted on stackoverflow so here is the reference to the page :

https://stackoverflow.com/questions/78592175/hinting-a-known-feasible-solution-to-a-milp-solver-with-google-ortools-mathopt-i

[Mizux]

Looking for Solutionhint in ortools/math_opt/... src.

or-tools/ortools/math_opt/core/python/solver_test.py

Lines 191 to 209 in ef7bb07

	def test_solution_hint_is_used(self, use_solver_class: bool) -> None:
	model = _build_simple_model()
	solution_hint = model_parameters_pb2.SolutionHintProto()
	solution_hint.variable_values.ids.append(0)
	solution_hint.variable_values.values.append(1.0)
	# Limit the solver so that it does not find a solution other than provided.
	result = _solve_model(
	model,
	use_solver_class=use_solver_class,
	solver_type=parameters_pb2.SOLVER_TYPE_GSCIP,
	parameters=parameters_pb2.SolveParametersProto(
	node_limit=0,
	heuristics=parameters_pb2.EMPHASIS_OFF,
	presolve=parameters_pb2.EMPHASIS_OFF,
	),
	model_parameters=model_parameters_pb2.ModelSolveParametersProto(
	solution_hints=[solution_hint]
	),
	)

or

or-tools/ortools/math_opt/python/model_parameters_test.py

Lines 28 to 38 in ef7bb07

	def test_solution_hint_round_trip(self) -> None:
	mod = model.Model(name="test_model")
	x = mod.add_binary_variable(name="x")
	y = mod.add_binary_variable(name="y")
	c = mod.add_linear_constraint(lb=0.0, ub=1.0, name="c")
	d = mod.add_linear_constraint(lb=0.0, ub=1.0, name="d")
	hint = model_parameters.SolutionHint(
	variable_values={x: 2.0, y: 3.0}, dual_values={c: 4.0, d: 5.0}
	)
	hint_round_trip = model_parameters.parse_solution_hint(hint.to_proto(), mod)

[Sacropyne]

Looking for Solutionhint in ortools/math_opt/... src.

or-tools/ortools/math_opt/core/python/solver_test.py

Lines 191 to 209 in ef7bb07

	def test_solution_hint_is_used(self, use_solver_class: bool) -> None:
	model = _build_simple_model()
	solution_hint = model_parameters_pb2.SolutionHintProto()
	solution_hint.variable_values.ids.append(0)
	solution_hint.variable_values.values.append(1.0)
	# Limit the solver so that it does not find a solution other than provided.
	result = _solve_model(
	model,
	use_solver_class=use_solver_class,
	solver_type=parameters_pb2.SOLVER_TYPE_GSCIP,
	parameters=parameters_pb2.SolveParametersProto(
	node_limit=0,
	heuristics=parameters_pb2.EMPHASIS_OFF,
	presolve=parameters_pb2.EMPHASIS_OFF,
	),
	model_parameters=model_parameters_pb2.ModelSolveParametersProto(
	solution_hints=[solution_hint]
	),
	)

or

or-tools/ortools/math_opt/python/model_parameters_test.py

Lines 28 to 38 in ef7bb07

	def test_solution_hint_round_trip(self) -> None:
	mod = model.Model(name="test_model")
	x = mod.add_binary_variable(name="x")
	y = mod.add_binary_variable(name="y")
	c = mod.add_linear_constraint(lb=0.0, ub=1.0, name="c")
	d = mod.add_linear_constraint(lb=0.0, ub=1.0, name="d")
	hint = model_parameters.SolutionHint(
	variable_values={x: 2.0, y: 3.0}, dual_values={c: 4.0, d: 5.0}
	)
	hint_round_trip = model_parameters.parse_solution_hint(hint.to_proto(), mod)

Thank you so much for your fast answer and sorry for not spotting these lines on my own.

I have tried to follow your second example, through this piece of code that is executed after a first optimization (to perform bi-criteria lexicographical optimization) :

# Initial solution
initial_solution_dictionary = dict()
for l in range(M):
    initial_solution_dictionary[all_vars[f"selection_{l+1}"]] = milp_result.variable_values(all_vars[f"selection_{l+1}"])
initial_solution = model_parameters.SolutionHint(initial_solution_dictionary)

# Second optim
milp.add_linear_constraint(all_vars[f"min"] >= milp_result.objective_value())

# Criterion : minimization of the number of selected slats
milp.maximize((1/(N*(N-1)/2))*(mathopt.fast_sum([all_vars[f"distance_{l+1}_{ll+1}"] for l in range(M) for ll in range(M) if ll>l])-distances.max()*(M*(M-1)/2-N*(N-1)/2)))

# Launch
params = mathopt.SolveParameters(enable_output=True)
model_params = model_parameters.ModelSolveParameters()
model_params.solution_hints.append(initial_solution)
milp_result = mathopt.solve(milp, mathopt.SolverType.HIGHS, params=params,model_params=model_params)

It runs without error but it looks like Highs is insensitive to the provided hint, it behaves just like when it’s not there. Is it maybe that the functionality is not there yet for Highs through mathopt ? Or am I still missing something in how I should use these classes and methods ?

[rma350]

If you look in this file:

https://github.com/google/or-tools/blob/stable/ortools/math_opt/solvers/highs_solver.cc

You see that hint is not supported for HiGHS yet (it is just silently ignored).

Gurobi, CP-SAT, and SCIP all support hint if this feature is critical. Gurobi and SCIP also support incremental MIP solving, which might buy you a little more than the hint if you are just changing the objective and resolving. Gurobi also has its own hierarchial objectives which we have limitted support for.