Reformulating optimization problem with normalization constraints

Specific Domains Optimization (Mathematical)
,
1

Hi! I’m pretty new to julia and optimization, and I’m trying to set up a optimization problem over a decision variable X \in \mathbb{R}^{m \times n} that would semantically capture assignment of “targets” in the rows of the matrix to “candidates” in the columns. One objective in this problem is based on maximization of “similarity” (encoded by symmetric matrix T \in \mathbb{R}^{m \times m}) of targets assigned to the same candidate. I am currently using an indicator variable Y \in \mathbb{R}^{m \times m \times n}, where Y_{ijk} indicates whether targets i and j are assigned to candidate k.
The working version of this objective is below:

\max_{X \in \{0,1\}^{m \times n}} \sum_{k=1}^n \sum_{i=1}^m \sum_{j=1}^m Y_{ijk} * T_{ij}

However, I am struggling to modify the above objective to address the bias in the assignment of all targets to one candidate. I want to somehow normalize each candidate’s “reward” by the number of targets assigned to that candidate:

\max_{X \in \{0,1\}^{m \times n}} \sum_{k=1}^n \cfrac{\sum_{i=1}^m \sum_{j=1}^m Y_{ijk} * T_{ij}}{(\sum_{i=1}^m X_{ik}) + 1}

However, an implementation of this modified objective gives me the error:

The solver does not support an objective function of type MathOptInterface.ScalarNonlinearFunction

Any feedback would be very much appreciated! For reference, my code is below:

# Define the decision variable
@variable(model, 0 <= X[1:m, 1:n] <= 1)
# Construct indicator variable
@variable(model, 0 <= Y[1:m, 1:m, 1:n] <= 1)
# Construct variable for column sums of X
@variable(model, c[1:n])

# Add constraints: Y_ijk <= X_ik and Y_ijk <= X_jk
for i in 1:m, j in 1:m, k in 1:n
    @constraint(model, Y[i, j, k] <= X[i, k])
    @constraint(model, Y[i, j, k] <= X[j, k])
end

# Add constraint: column sums of c
for j in 1:n
    @constraint(model, c[j] == sum(X[i, j] for i in 1:m) + 1)
end

# Add constraints: row sums over X == 1
@constraint(model, [i=1:m], sum(X[i, j] for j in 1:n) == 1)

first_objective = 0.0
for k in 1:n
    sum_Y_T = sum(Y[i, j, k] * T[i, j] for i in 1:m, j in 1:m)
    # Note: non-normed objective that does not divide by c[k] works here
    first_objective += sum_Y_T / c[k]
end

@objective(model, Max, first_objective)
2

The error you see is because the denominator turns your program from a linear to a nonlinear integer program, which is not supported by your choice of solver (presumably HiGHS) and much harder in general.
I would suggest you stick to a linear formulation. Maybe you could just add another variable counting the targets assigned to each candidate, and another term in the objective that penalizes the distance between these quantities for ech pair of candidates?

1 Like
3

Let’s say I would expect to see a right skew in the distribution of the number of targets assigned to each candidate (that is, many candidates with one or two targets and just a few candidates with very many targets). Is there a way to add a penalty that wouldn’t be adversarial to this expectation?

For example, would it make sense to take the variable counting the targets assigned to each candidate c \in \mathbb{W}^n and add a penalty \lambda \sum_{j=1}^n c_j ^2, where \lambda is estimated by the average over all cells in T?

4

Sure, that’s possible too. Just keep in mind that every jump in complexity of the objective implies slower solve times. This transformation would turn your integer LP (linear program) into an integer QP (quadratic program). If your instance is small enough it’s fine though, so I recommend you try it. But definitely avoid non-quadratic penalties if you can.

1 Like