Define a correct constraint, like outside a 2-D rectangle in Julia with JuMP

Question

I would like to define a constraint in an optimization problem as follows: (x,y) not in {(x,y)|1.0 < x < 2.0, 3.0 < y < 4.0}.

what I tried is @constraint(model, (1.0 < x < 2.0 + 3.0 < y < 4.0)!=2), but failed. It seems that boolen operation is not allowed. such that I have no idea about it. Any advice is appreciated!

Probably you mean `3.0 < y < 4.0`, because as it is written, it's an empty condition (i.e. no satisfying `y`) — Dan Getz, Jan 07 '23 at 15:45

Przemyslaw Szufel · Answer 1 · 2023-01-07T23:30:33.767

2

You should avoid introducing quadratic constraints (as in the other answer) and rather introduce binary variables. This increase number of available solvers and generally linear models take shorter time to solve.

Hence you should note that !(1.0 < x < 2.0) is an equivalent of x <= 1 || x >= 2 which can be written in a linear form as:

@variable(model, bx, Bin)
const M = 1000 # number "big enough"
@constraint(model, x <= 1 + M*bx)
@constraint(model, x >=2 - M*(1-bx))

bx is here a "switcher" variable that makes either first or second constraint obligatory.

I am not sure what you want about y as you have 3.0 < y < 3.0 but basically the pattern to formulate the would be the same. Just note you cannot have a constraint such as y != 3 as solvers obviously have some numerical accuracy and you would need rather to represent this is as for an example !(3-0.01 < y < 3+0.01) (still using the same pattern as above)

edited Jan 07 '23 at 23:30

answered Jan 07 '23 at 20:42

Przemyslaw Szufel

40,002
3
32
62

Sorry, I make a mistake here. It should be 3.0 < y < 4.0 – Quinn Xie Jan 08 '23 at 13:44
It is a good idea to add a “switcher”. – Quinn Xie Jan 08 '23 at 13:45
1

Yes you will need to have a set of switchers for (x <= 1 || x >= 2) || (y <= 3 || y >= 4) – Przemyslaw Szufel Jan 08 '23 at 16:54

Dan Getz · Answer 2 · 2023-01-08T22:29:31.413

0

UPDATE: The previous solution in this answer turned out to be wrong (exclude parts of the admissable region), and so I felt obligated to provide another 'right' solution. This solution partitions the admissable region into parts and solves different optimization problems for each part. Keeping the best solution. This is not a nice solution, but if one does not have a good solver (those commercial ones) it is one way. The commercial solvers usually go through a more efficient similar process by the name of branch-and-bound.

using JuMP, Ipopt

function solveopt()
    bestobj = Inf
    bestx, besty = 0.0,0.0
    for (ltside, xvar, val) in (
      (true, true, 2.0),(false, true, 3.0),
      (true, false, 3.0),(false, false, 4.0))
        m = Model(Ipopt.Optimizer)
        @variable(m, x)
        @variable(m, y)
        add_constraint(m, ScalarConstraint(xvar ? x : y,
          ltside ? MOI.LessThan(val) : MOI.GreaterThan(val)))

        # following is an objective optimal inside the box
        @NLobjective(m, Min, (x-2.5)^2+(y-3.5)^2)

        optimize!(m)
        if objective_value(m) < bestobj
            bestx, besty = value(x), value(y)
        end
    end
    return bestx, besty
end

The solution for this example problem is:

julia> solveopt()
:
: lots of solver output...
:
(2.5, 3.9999999625176965)

Lastly, I benchmarked this crude method against a non-commercial solver (Pajarito) with the method from other answer and this one is 2X faster (because of simplicity, I suppose). Commercial solvers would beat both times.

edited Jan 08 '23 at 22:29

answered Jan 07 '23 at 15:44

Dan Getz

17,002
2
23
41

2

You can avoid quadratic expression by adding a binary variable – Przemyslaw Szufel Jan 07 '23 at 20:42
@PrzemyslawSzufel Knew there was a better way to do this, but wasn't sure, so putting out any method is a good way to find out better ways to do it :). – Dan Getz Jan 07 '23 at 22:13
sure! sometimes solvers do reformulations anyway. but it is always better to use the direct method :) – Przemyslaw Szufel Jan 07 '23 at 23:28
@PrzemyslawSzufel Which solver should I use? I've tried comparing (for performance) this method with the Boolean method, but IpOpt refused binary, and HiGHs refuses quadratic objective. – Dan Getz Jan 07 '23 at 23:41
As a rule of thumb use binary. Linear model is almost always better than nonlinear one. Especially if you are able to set a feasible initial starting solution (sometimes it is difficult for solver to find the first solution). Quadratic constraints make models much harder. There might be some exceptions of course. – Przemyslaw Szufel Jan 08 '23 at 00:14
@PrzemyslawSzufel Sure, just wanted a recommendation for a solver which supports both quadratic obejctive and mixed-integer/boolean variables. – Dan Getz Jan 08 '23 at 00:27
1

All commercial solvers (Eg. Gurobi, CPLEX) do both and you can mix binary with quadratic even in one model. As far as open source goes try Juniper and Pajarito - however as far as I remember you will not be able to solve huge models with these. For a full list of solver capabilities see https://jump.dev/JuMP.jl/stable/installation/ – Przemyslaw Szufel Jan 08 '23 at 09:14

Define a correct constraint, like outside a 2-D rectangle in Julia with JuMP

2 Answers2