I have an optimisation problem that is essentially a knapsack problem with a non-linear objective.

I have an input dataframe that contains a row for each item, each item has columns defining its mean value and weight. I also have a covariance matrix that contains the variances and covariances between each item.

I take this information and simulate the values for each item a number of times, and store that data.

Then i define my optimisation problem, where i want to select 20 groups of 6 items, so that i maximise the probability of any one of these groups reaching a target value.

Essentially, I am trying to maximise:

$$P(max(x) > T)$$

where x is the values of the groups of lineups, and T is the target score.

My current method:

I am using pyomo in python to solve this problem. First I define a binary decision variable and some constraints, such as making sure no groups are identical and that they are under the weight limit, then i define the objective rule.

I try and do this by summing the simulated scores for each group of items, doing this for each simulation, and keeping track of the number of times the value reaches the target value.

I then try to solve the problem using the solver.

However, when i run it, the model does not initialise values for the binary decision variable, i assume because it cannot find a solution. When i initialise the values myself with groups that make sense, it runs through and calculates the probability, but does not change any of the groups at all.

Here is my current attempt:

# Define input data
n_items = 120
m_groups = 20
target_value = 400
n_simulations = 10000

# Generate simulated scores for all players in the tournament
simulated_scores = multivariate_normal.rvs(mean=df['value'], cov=cov_mat, size=n_simulations)

# Define model
model = ConcreteModel()

# Define decision variables with initial values
model.x = Var(range(n_items), range(m_groups), within=Binary, initialize=0)

def objective_rule(model):
    prob = 0
    for j in range(m_groups):
        # Get indices of selected players in lineup j
        for s in range(n_simulations):
            sim_scores = sum(model.x[i,j] * simulated_scores[s, i] for i in range(n_items))
            if value(sim_scores) > target_value:
                prob += 1
    total_prob = prob / (n_simulations*20)   
    return total_prob

model.objective = Objective(rule=objective_rule, sense=maximize)

# Define constraints
model.players_per_lineup = ConstraintList()
for j in range(m_groups):
    model.players_per_lineup.add(sum(model.x[i,j] for i in range(n_items)) == 6)

model.group_per_item = ConstraintList()
for i in range(n_items):
    model.group_per_item.add(sum(model.x[i,j] for j in range(m_groups)) <= 3)

model.weight_limit = ConstraintList()
for j in range(m_groups):
    model.weight_limit.add(sum(model.x[i,j] * df.iloc[i]['weights'] for i in range(n_items)) <= 300)

# Solve model
solver = SolverFactory('glpk')

I assume this is not working as I am not fully understanding the extent of this optimisation problem, and taking a simplistic approach that cannot be solved using this method.

I'm looking for a simple way to produce a solution for this non-linear problem that produces the optimal groups of items. Ideally something that works with simulations that are not always normally distributed.

  • $\begingroup$ 1) Why do you think the problem you have is a non-linear program? 2) Also, it seems you are trying to solve a multi-objective function. It would be worth if, you can write the problem in a mathematical form. $\endgroup$
    – A.Omidi
    Apr 15, 2023 at 6:56
  • $\begingroup$ @A.Omidi I assume as the objective is to maximise a probability, and the equation for probability is non linear, it is a non-linear problem. I’m not sure if this is a correct assumption. I am not all that familiar with writing these problems in mathematical form, but can explain it in more detail if needed. I’m trying to maximise the probability of a group of 20 lists of 6 items reaching a target score - I have a weight constraint of 50000 for each list of 6 items, and each list must be exactly 6 items long. $\endgroup$
    – will
    Apr 16, 2023 at 16:31
  • $\begingroup$ You might be interested in this paper, which is motivated by fantasy sports but instead maximizes the expected maximum: pubsonline.informs.org/doi/abs/10.1287/ijoc.2022.1259 $\endgroup$
    – RobPratt
    Apr 17, 2023 at 20:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.