# What JuMP algorithm to use for this optimization problem?

**URL:** <https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936>\
**Category:** Optimization (Mathematical)\
**Tags:** jump\
**Created:** [November 24, 2018, 4:11am UTC](https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936 "2018-11-24T04:11:13Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![tyleransom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tyleransom/32/530_2.png) [@tyleransom](https://discourse.julialang.org/u/tyleransom)\
**Post date:** [November 24, 2018, 4:11am UTC](https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936/1 "2018-11-24T04:11:13Z")

</div>

I have a question about what type of algorithm I should be using for a fairly straightforward optimization problem.

I have the [following data](https://gist.github.com/tyleransom/3738fa6cd1b3b5602e0621b08d068380)

```julia
id,val,score,id1
1,9,0,64
2,4,0,7
3,11,12,53
4,7,0,8
5,4,35,11
6,14,0,31
7,13,29,2
8,10,11,4
9,2,18,18
10,5,6,38
...

```

I want to choose 3 “good” `id`s and 3 “bad” `id`s. Without loss of generality, number these 1,2,3 and 4,5,6 respectively. Choose these 6 `id`s to **maximize** :

`objective = score[1]+score[2]+score[3]-score[4]-score[5]-score[6]`

subject to

```julia
constraint1: val[1]+val[2]+val[3] >= val[4]+val[5]+val[6]
constraint2: id[1] !in [id1[4],id1[5],id1[6]]
constraint3: id[2] !in [id1[4],id1[5],id1[6]]
constraint4: id[3] !in [id1[4],id1[5],id1[6]]

```

This seems like something JuMP would very easily handle. I’m just not quite sure where to start. Any help would be greatly appreciated!

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [November 24, 2018, 4:24am UTC](https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936/2 "2018-11-24T04:24:22Z")

</div>

Yes, I think JuMP would work very well here. Your problem looks like it could be solved as a mixed-integer linear program (MILP). Solvers like GLPK (free) and Gurobi (commercial) handle problems in this form and work with JuMP.

I would suggest creating two binary variables for each ID: `is_good[1:N]` and `is_bad[1:N]`. Your last three constraints are just something like:

```julia
is_good[1:N] .+ is_bad[1:N] .<= 1

```

and your objective function is, roughly:

```julia
score[i] * is_good[i] - score[i] * is_bad[i] for i in 1:N

```

I can provide more details if you need, but hopefully this should at least get you going in the right direction.

---

<div class="post-metadata">

**Author:** ![tyleransom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tyleransom/32/530_2.png) [@tyleransom](https://discourse.julialang.org/u/tyleransom)\
**Post date:** [November 24, 2018, 4:25am UTC](https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936/3 "2018-11-24T04:25:41Z")

</div>

Thank you! I’ll give it a shot.

---

<div class="post-metadata">

**Author:** ![tyleransom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tyleransom/32/530_2.png) [@tyleransom](https://discourse.julialang.org/u/tyleransom)\
**Post date:** [November 24, 2018, 2:16pm UTC](https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936/4 "2018-11-24T14:16:20Z")

</div>

Here’s my first (unsuccessful) attempt at it:

```julia
using DataFrames
using HTTP
using uCSV
using JuMP
using GLPK
using Cbc

# read in the data
fname = "https://gist.githubusercontent.com/tyleransom/3738fa6cd1b3b5602e0621b08d068380/raw/5c4b139639d7b3c16716289b0232b8528d1bf494/mwe.csv"
data = DataFrame(uCSV.read(IOBuffer(HTTP.get(fname).body), quotes='"', header=1))
data = Matrix(data)

# id = data[:,1]
# val = data[:,2]
# score = data[:,3]
# id1 = data[:,4]

# take a subset of the data just to compare (can figure out by hand on smaller data)
data = data[1:14,:] 

#solver = GLPKSolverLP()
solver = CbcSolver()

# Solve model
function SolveModel(data)
    N = size(data,1) 
    m = Model(solver=solver)

    @variable(m, is_good[1:N], Bin)
    @variable(m, is_bad[1:N], Bin)

    @objective(m, Max, data[i,3] * is_good[i] - data[i,3] * is_bad[i] for i in 1:N)

    @constraints m begin
        # Constraint 1 - sum of good vals >= sum of bad vals
        data[i,2] * is_good[i] .>= data[i,2] * is_bad[i]
        # Constraint 2 - can't choose the same id for both good and bad
        is_good[1:N] .+ is_bad[1:N] .<= 1
    end

    # Solve it
    status = solve(m)
    println(getvalue(is_good))
    println(getvalue(is_bad))
end

@time SolveModel(data)

```

Full code in gist from is [here](https://gist.github.com/tyleransom/3738fa6cd1b3b5602e0621b08d068380#file-jump_mwe-jl). I’m getting an error:

```julia
ERROR: LoadError: MethodError: no method matching *(::Float64, ::Base.Generator{UnitRange{Int64},getfield(Main, Symbol("##9#10")){Array{Int64,2},Array{Variable,1},Array{Variable,1}}})
Closest candidates are:
  *(::Any, ::Any, ::Any, ::Any...) at operators.jl:502
  *(::Float64, ::Float64) at float.jl:399
  *(::AbstractFloat, ::Bool) at bool.jl:120

```

Full StackTrace is available [here](https://gist.githubusercontent.com/tyleransom/3738fa6cd1b3b5602e0621b08d068380/raw/5b18ff7dcb1893bfa1568681c9092e2e52e72f40/jump_mwe.log).

I really appreciate your help!

---

<div class="post-metadata">

**Author:** ![tkoolen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkoolen/32/1603_2.png) [@tkoolen](https://discourse.julialang.org/u/tkoolen)\
**Post date:** [November 24, 2018, 5:37pm UTC](https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936/5 "2018-11-24T17:37:18Z")

</div>

> ```julia
> @objective(m, Max, data[i,3] * is_good[i] - data[i,3] * is_bad[i] for i in 1:N)
> 
> ```

`sum`?

> ```julia
> data[i,2] * is_good[i] .>= data[i,2] * is_bad[i]
> 
> ```

`sum(data[i,2] * is_good[i] for i = 1 : N) >= sum(data[i,2] * is_bad[i] for i = 1 : N)`?

---

<div class="post-metadata">

**Author:** ![tyleransom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tyleransom/32/530_2.png) [@tyleransom](https://discourse.julialang.org/u/tyleransom)\
**Post date:** [November 24, 2018, 7:16pm UTC](https://discourse.julialang.org/t/what-jump-algorithm-to-use-for-this-optimization-problem/17936/6 "2018-11-24T19:16:16Z")

</div>

Thanks! That did the trick.