Help with setting up a JuMP model to give an even 'spread' of samples

Specific Domains Optimization (Mathematical)
1

Hi everyone,

I’m trying to learn optimization alongside JuMP syntax, and as a toy problem, I’m trying an integer based problem, in which I have a variable y, with decision variables x (in [0,1]), and I want to be able to optimize such that the decision variables are uniformly spread through the domain of y.

m = Model();
y = collect(1.0:1.0:100);
n = length(y);
@variable(m, x[1:n], Bin);
@constraint(m, sum(x) == 10);

Any ideas about what the best objective would be for this, and the accompanying best (preferably open source) solver?

2

Assuming that y is uni-variate and sorted, maximize the minimum difference between two adjacent points.

julia> using JuMP

julia> import HiGHS

julia> function main(; y, N)
           n = length(y)
           model = Model(HiGHS.Optimizer)
           set_silent(model)
           @variable(model, x[1:N, 1:n], Bin)
           @variable(model, t)
           @expression(model, fx[i=1:N], y' * x[i, :])
           @constraint(model, [i=1:N], sum(x[i, :]) == 1)
           @constraint(model, [i=2:N], t <= fx[i] - fx[i-1])
           @objective(model, Max, t)
           optimize!(model)
           return value.(fx)
       end
main (generic function with 1 method)

julia> main(; y = 1.0:1.0:100, N = 10)
10-element Vector{Float64}:
   1.0
  12.0
  23.0
  34.00000000000002
  45.0
  55.99999999999991
  67.0
  78.00000000000004
  89.0
 100.0

julia> y = 100 * sort!(rand(10))
10-element Vector{Float64}:
  3.0924795270613537
 29.994215960126304
 30.68411127002588
 41.37110956728867
 52.792561205720624
 65.56521771454567
 73.50137345814962
 78.05039674417431
 89.7630154791887
 97.49022496748074

julia> main(; y = y, N = 3)
3-element Vector{Float64}:
  3.0924795270613537
 52.792561205720624
 97.49022496748074
1 Like
3

Thanks! This is just what I needed - I was thinking of using the differences between adjacent points, but wasn’t sure how to implement. If it wasn’t sorted (which may be the case if I’m trying to optimize over multiple variables), could I just compute a vector of ranks and use that instead?

4

If the points aren’t sorted, then yes, just sort them first, optimize, and then unsort to the original permutation.

If it’s not one-dimensional, then the problem is a lot harder and there isn’t an obvious solution.