Parametrize JuMP problem for repeat evaluation?

Specific Domains Optimization (Mathematical)
1

Hi all,

I have got at JuMP.jl problem. I have the following discrete optimization problem:

	using JuMP, Cbc
	function best_bundle(;m=10,b=2)
		srand(1)
		# m = courses available
		k = 5 # courses to take
		price = collect(linspace(0.1,1,m))
		prefs = collect(linspace(0.1,1,m))

		println("price = $price")
		println("prefs = $prefs")

		model = Model(solver=CbcSolver())
		@variable(model, x[1:m] >= 0, Bin)  

		# objective: sum of preferences
		@objective(model, Max, dot(prefs,x) )

		# constraint: cost is less than budget
		@constraint(model, dot(price,x) <= b )

		# can only choose k courses out of all m
		@constraint(model, sum(x) <= k )

		status =solve(model)
		println("Objective is: ", getobjectivevalue(model))
		println("Solution is:")
		println("find(x) = $(find(getvalue(x)))")
		println("total cost = $(dot(price,getvalue(x)))")


	end
julia> best_bundle(b=3)
price = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
prefs = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
Objective is: 3.0
Solution is:
find(x) = [2, 4, 6, 8, 10]
total cost = 3.0

I need to run call this function for many different values of b, and eventually for many different versions of prefs, but that should be equivalent. I was wondering if there is a way to set up the problem once in the beginning, parameterized by b, which would allow evaluating any given problem best_bundle(b) faster (without having to do the setup tasks of a standard JuMP problem). thanks!

2

For b, you can already do it using setRHS. For prefs (updating the objective function), you’ll have to wait for the new MathOptInterface-backed version of JuMP, via modifyobjective! or set!(optimizer, ObjectiveFunction(), ...), or whatever interface JuMP will expose that calls these functions.

3

You can actually change the objective by calling @objective again. e.g.

m = Model()
@variable(m, x >= 0)
@objective(m, Min, x)
solve(m)
@objective(m, Max, -x)
solve(m)

Changing constraint coefficients is not exposed at a JuMP level, but there is MathProgBase support although not all solvers will support this.

JuMP 0.19 will fix these issues.

4

thanks both, thats very helpful.
Just to be sure I interpret what you are saying correctly. Suppose I adopt @odow s strategy, and suppose that I need to do this procedure 1_000_000 times. I am trying to understand what steps JuMP needs to perform each time, and whether doing those manually would mean any gains in terms of speed. for example, my understanding was that for this kind of problem, a relaxed continuous problem is solved first, then linear constraints are added until the solution lies in the discrete set of admissible values.
Question: does that relaxed solution require automatic differentiation gradients/hessians on behalf of JuMP? If so, I presume that is quite costly to do repeatedly. In a manual solution, could I provide those to Cbc in some way and call the solver directly 1_000_000 times?

I have just seen on the mathprogbase docs that my problem is really just a version of the knapsack problem, so my question relates to that I think.
thanks again!

5

JuMP takes your input, and transforms it into a format that can be fed to a solver. It is up to the solver to choose how to solve the problem.

If you modify the objective in JuMP, JuMP will recompute the objective coefficients and then the next time solve is called, update these in the solver. Going via MathProgBase will skip the JuMP step and deal directly with the solver. However, this will leave the JuMP model out of sync and you should probably only do this if you understand the consequences.

Question: does that relaxed solution require automatic differentiation gradients/hessians on behalf of JuMP?

No. The linear/conic part of JuMP is quite different to the nonlinear part. Integer programming is quite a large field. You may want to start by googling “linear programming” “integer programing” and “branch-and-bound”.

I would recommend just trying to solve your problem using the modifications described in the previous posts. I routinely solve millions of parameterized JuMP models in sequence using these techniques. The largest bottleneck in my models is the solve time rather than the problem modification. If Cbc is too slow, you may want to try commercial solvers like Gurobi (gurobi.com).

6

Great thanks !