2
$\begingroup$

I have a number of variables each assigned an integer value. I need to split these variables in three groups with a predefined number of variables going into each group while optimizing towards predefined sums of the values in each group. Each group sum should be as close as possible to the predefined value, but can be above or below. All variables should be used and each variable can only be used once.

For example, I might have 10 variables...

Variable Value
A1 98
A2 20
A3 30
A4 50
A5 18
A6 34
A7 43
A8 21
A9 32
A10 54

...and the goal could be to create three groups:

Group #Variables Sum optimized towards
X 6 200
Y 2 100
Z 2 100

So group X should hold 6 variables and their sums should be as close as possible to 200 - but I need to optimize for each of the groups simultanously.

I've tried to set up PuLP to perform this task. I seem to have found a solution for creating a single group, but I cannot figure out how to split the variables into groups and optimize the assignments based on the sums for each group. Is there a way to do this?

Below is my code for producing the first group with the presented variables.

from pulp import LpMaximize, LpMinimize, LpProblem, lpSum, LpVariable, PULP_CBC_CMD, value, LpStatus

keys = ["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "A10"]
data = [98,20,30,50,20,34,43,21,32,54]

problem_name = 'repex'

prob = LpProblem(problem_name, LpMaximize)

optiSum = 200 # Optimize towards this sum
variableCount = 6 # Number of variables that should be in the group

# Create decision variables
decision_variables = []
for i,n in enumerate(data):
    variable = i
    variable = LpVariable(str(variable), lowBound = 0, upBound = 1, cat= 'Binary')
    decision_variables.append(variable)


# Add constraints
sumConstraint = "" # Constraint on sum of data elements
for i, n in enumerate(decision_variables):
    formula = data[i]*n
    sumConstraint += formula

countConstraint = "" # Constrain on number of elements used
for i, n in enumerate(decision_variables):
        formula = n
        countConstraint += formula

prob += (sumConstraint <= optiSum)
prob += (countConstraint == variableCount)
prob += sumConstraint

# Solve
optimization_result = prob.solve(PULP_CBC_CMD(msg=0))
prob.writeLP(problem_name + ".lp" )
print("Status:", LpStatus[prob.status])
print("Optimal Solution to the problem: ", value(prob.objective))
print ("Individual decision_variables: ")
for v in prob.variables():
    print(v.name, "=", v.varValue)

Which produces the following output:

Status: Optimal
Optimal Solution to the problem:  200.0
Individual decision_variables:
0 = 0.0
1 = 1.0
2 = 0.0
3 = 1.0
4 = 0.0
5 = 1.0
6 = 1.0
7 = 1.0
8 = 1.0
9 = 0.0
$\endgroup$

1 Answer 1

1
$\begingroup$

Let $N_g$ be the number of variables you need to assign to group $g,$ $V_g$ the target sum for group $g,$ and $a_v$ the value assigned to variable $v.$ I'm going to assume you measure "closeness" via absolute values ($L_1$ norm).

We will use binary variables $x_{v,g}$ to indicate whether variable $v$ is assigned to group $g,$ continuous variables $s_g$ to capture the sum of the values assigned to each group $g,$ and nonnegative variables $d_g=\vert s_g-V_g\vert$ to capture the absolute deviations from group targets. The objective is to minimize $\sum_g d_g,$ the total absolute error in group sums. The constraints are as follows: $$\sum_{g}x_{v,g} =1\quad \forall v$$(assign each variable to exactly one group), $$\sum_{v}x_{v,g} =N_{g}\quad \forall g$$(assign the desired number of variables to each group), $$s_{g} =\sum_{v}a_{v}x_{v,g} \quad \forall g$$(defining the sum $s_g$ of each group), and finally $$d_{g} \ge s_{g}-V_{g}\quad \forall g$$and$$d_{g} \ge V_{g}-s_{g}\quad \forall g$$(forcing $d_g$ to be the absolute difference $\vert s_g-V_g\vert$).

$\endgroup$
2
  • $\begingroup$ Thanks @prubin. As for objective I'd elaborate as Min $d^+_g + d^-_g$ $\endgroup$ Nov 16, 2022 at 21:35
  • $\begingroup$ In my formulation, $d_g\ge 0,$ so $d_g^+ + d_g^- = d_g.$ I caught a typo in the objective (which I have fixed). You want to minimize the sum of the $d_g$ variables. $\endgroup$
    – prubin
    Nov 16, 2022 at 23:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.