All solutions of linear program

Specific Domains Optimization (Mathematical)
1

if I have the following model

	VC_model2 = direct_model(Gurobi.Optimizer())
	@variable(VC_model2, y[i=initial:n], binary=true)
	@variable(VC_model2, x[i=initial:n], binary=true)
	################################################
	@constraint(VC_model2, sum(x[j] for j in initial:n) == k_val)
	for j=initial:n
		@constraint(VC_model2,y[j] <= sum(x[i] for (j,i) in E))
	end
	@objective(VC_model2, Max, sum(y[j] for j in initial:n))
	optimize!(VC_model2)

there is any way that gurobi can help to get all the possible solutions of the model?

2

I do not know if Gurobi can achieve that. But you could solve your model in a loop, and cut off each found solution by adding no-good-cuts (as new constraints) until the objective value changes (i.e., then you have cut off all optimal solutions of your initial model).

3

Perhaps a good question would be: why do you want to get all solutions?

1 Like
4

I think the question is not Gurobi specific. Alternative solutions might be sought by adding extra constraints and checking the objective value in each try.

5

In many cases, alternative optimum solutions provide a menu for the decision maker.

6

JuMP and Gurobi support returning some solutions. Use result_count(model) to see how many it found. For details, see: Solutions · JuMP

But this isn’t the same as all solutions. As @mike_k suggests, you’d have to do some iterative method, where you added no-good cuts to remove the solution you just found: valid inequalities - No-good cuts for general integer variables - Operations Research Stack Exchange

7

You may find this tutorial post helpful: Finding multiple feasible solutions.

It could be used in conjunction with first solving the model once and imposing the optimal objective value as new constraint: objective function == optimal value of first solve.

2 Likes