# Optimize 0-1 loss in MIP

**URL:** <https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027>\
**Category:** Optimization (Mathematical)\
**Created:** [January 6, 2020, 3:14pm UTC](https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027 "2020-01-06T15:14:52Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Maximilian](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maximilian/32/12206_2.png) [@Maximilian](https://discourse.julialang.org/u/Maximilian)\
**Post date:** [January 6, 2020, 3:14pm UTC](https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027/1 "2020-01-06T15:14:52Z")

</div>

I am currently trying to solve the following optimization problem

 ![Objective](https://global.discourse-cdn.com/julialang/original/3X/f/f/ff776d800a307a0a91eed910287a542277c8821b.jpeg)

Where N is the number of observations on \mathbf{x} predictors, and y \in \{-1, 1\} is a binary vector of length N, \lambda has to be integer, C\_0, C\_1 are tuning parameters penalizing complexity of the model. Illustrative example: suppose you would like to predict if a mushroom is poisonous (y) and have predictors like its odor and it’s color (x\_1, x\_2). I would like to obtain a solution similar to this:

 ![](https://global.discourse-cdn.com/julialang/original/3X/e/3/e3e9a1c2fdab2603059cd351b25dca859c30618a.png)

However, I am new to optimization problems (I have a statistical background) and thought I’d be a nice opportunity to get to know Julia better.  
Now I am a bit lost - I understood how to generally formulate and solve MIP problems with JuMP. However, I don’t know how to optimize the 0-1 loss between a predicted category and the actual category. Also, I don’t know how to formulate the first penalty term C\_0 ||\lambda||\_0 where ||\lambda||\_0 is one if lambda is nonzero, and 0 if \lambda is zero.

Any help, and also resources about such types of problems, would be greatly appreciated.

Pictures from  
Ustun, B., Traca, S., & Rudin, C. (2013). Supersparse linear integer models for interpretable classification. _arXiv preprint arXiv:1306.6677_ .

---

<div class="post-metadata">

**Author:** ![leethargo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leethargo/32/6004_2.png) [@leethargo](https://discourse.julialang.org/u/leethargo)\
**Post date:** [January 8, 2020, 11:18am UTC](https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027/2 "2020-01-08T11:18:43Z")

</div>

I believe the paper you mention actually provides a full MIP formulation.

In any case, to represent the “0-norm”, you could introduce a binary variable a\_j \in \{0, 1\} for every component j of \lambda. Then you can minimize the C\_0\sum\_j a\_j.  
You also need to add constraints of the form \lambda\_j \ge M a\_j where M is a suitable upper bound on the values that \lambda can take.

---

<div class="post-metadata">

**Author:** ![robertfeldt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/robertfeldt/32/239_2.png) [@robertfeldt](https://discourse.julialang.org/u/robertfeldt)\
**Post date:** [May 2, 2020, 12:11am UTC](https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027/3 "2020-05-02T00:11:54Z")

</div>

@Maximilian did you find a solution to representing 0-1 Loss in JuMP? When I try this:

```julia
loss01 = @expression(model, (y .* (X * lambda)) .<= 0.0)

```

I get a MethodError:

```julia
ERROR: MethodError: no method matching isless(::GenericAffExpr{Float64,VariableRef}, ::Float64)

```

Any tricks to handle this?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [May 2, 2020, 1:32am UTC](https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027/4 "2020-05-02T01:32:55Z")

</div>

Use `@constraint` instead of `@expression`. Take a read of the [JuMP documentation](https://www.juliaopt.org/JuMP.jl/stable/) under “constraints” and “expressions.”

---

<div class="post-metadata">

**Author:** ![robertfeldt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/robertfeldt/32/239_2.png) [@robertfeldt](https://discourse.julialang.org/u/robertfeldt)\
**Post date:** [May 2, 2020, 6:15pm UTC](https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027/5 "2020-05-02T18:15:42Z")

</div>

Thanks, but this is not a constraint. It is a part of a larger expression that is to be in the objective. So not clear one can use contraint instead.

---

<div class="post-metadata">

**Author:** ![leethargo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leethargo/32/6004_2.png) [@leethargo](https://discourse.julialang.org/u/leethargo)\
**Post date:** [May 2, 2020, 7:18pm UTC](https://discourse.julialang.org/t/optimize-0-1-loss-in-mip/33027/6 "2020-05-02T19:18:18Z")

</div>

But in that case, you can’t use `<=`. The `@expression` should probably only cover the left-hand side of the inequality?