I have a bag of scale weights and some pressure plates that need to be fully pressed.

After distributing all the weights there is a penalty for each plate that isn't completely pressed down.

The base penalty is unique to each plate. The final penalty given after the weights are distributed for not fully pressed plates is a equal to how pressed down the plate was + a fraction of the base penalty.

For example if a plate has half the weight it needs, (lets say 5gr / 10gr) and a base penalty P1, the total penalty would be 50% * P1 from half the weights + an extra arbitrary fraction for all plates that are not fully pressed, such as 30% * P1.

If another plate needs 15gr and has a 20gr weight on top of it it is fully pressed down and there is no penalty for that plate. (But an extra 5gr of weight gets wasted.)

Is there a way to look for the optimal way / algorithm to distribute the weights without brute forcing it and just trying all combinations? Can this problem be mapped to anything else that might be easier to solve?

Since I am just trying to map weights to plates I though it sounded like a bipartite graph but I am unsure how I would include the penalties. I am a bit lost.

Toy example as requested in the comments.

There are 2 plates and 3 weights. Plate 1 needs 4gr and has a base penalty of P1 = 20. Plate 2 needs 10gr and has a base penalty of P2 = 150.

The extra penalty coefficient can be 15%

There are 3 weights available to use. 2gr , 3gr and 4gr.

Using the 4g weight to cover the 1st plate reduces Penalty from plate 1 to 0 and leaves us with a 2gr and a 3gr weight.

Adding the remaining 5gr to plate 2 presses it by 5/10 = 50%.

So the penalty from plate 2 becomes 50% * 150 + 15% * 150 (extra 15% from failing to press the plate fully) for a total of 97.5

On the other hand ignoring plate 1 and putting all the weights on plate 2 results in the full 100% + 15% penalty from plate 1 (20 + 3) and 10% * P2 + 15% * P2 from plate 2 (15 + 22.5) totaling up to a penalty of 60.5

I have a bag of scale weights and some pressure plates that need to be fully pressed.

After distributing all the weights there is a penalty for each plate that isn't completely pressed down.

The base penalty is unique to each plate. The final penalty given after the weights are distributed for not fully pressed plates is a equal to how pressed down the plate was + a fraction of the base penalty.

For example if a plate has half the weight it needs, (lets say 5gr / 10gr) and a base penalty P1, the total penalty would be 50% * P1 from half the weights + an extra arbitrary fraction for all plates that are not fully pressed, such as 30% * P1.

If another plate needs 15gr and has a 20gr weight on top of it it is fully pressed down and there is no penalty for that plate. (But an extra 5gr of weight gets wasted.)

Is there a way to look for the optimal way / algorithm to distribute the weights without brute forcing it and just trying all combinations? Can this problem be mapped to anything else that might be easier to solve?

Since I am just trying to map weights to plates I though it sounded like a bipartite graph but I am unsure how I would include the penalties. I am a bit lost.

Toy example as requested in the comments.

There are 2 plates and 3 weights. Plate 1 needs 4gr and has a base penalty of P1 = 20. Plate 2 needs 10gr and has a base penalty of P2 = 150.

The extra penalty coefficient can be 15%

There are 3 weights available to use. 2gr , 3gr and 4gr.

Using the 4g weight to cover the 1st plate reduces Penalty from plate 1 to 0 and leaves us with a 2gr and a 3gr weight.

Adding the remaining 5gr to plate 2 presses it by 5/10 = 50%.

So the penalty from plate 2 becomes 50% * 150 + 15% * 150 (extra 15% from failing to press the plate fully) for a total of 97.5

On the other hand ignoring plate 1 and putting all the weights on plate 2 results in the full 100% + 15% penalty from plate 1 (20 + 3) and 10% * P2 + 15% * P2 from plate 2 (15 + 22.5) totaling up to a penalty of 60.5

• algorithm
• computer-science
• combinatorics

• This seems to be a classic resource allocation problem ( aka agents to tasks ). You want to optimize the allocation of the weights to the plates. You can use a maximum flow algorithm to solve this, or just go ahead and tackle it directly using integer linear programming. In your case, the penalty constraint suggests to me that linear programming will turn out to be the better approach ( the penalties will be minimized by stetting the objective function coefficients to the penalty values ) – ravenspoint Commented Mar 19 at 13:58
• 1 Can you put more than one weight on a plate? – Nick ODell Commented Mar 19 at 14:02
• It would be extremely helpful if you could provide two example problems. First a toy problem ( say two plates and three weights ) so I can check that I fully understand yoir problem description. Second a full scale 'real' problem for testing. – ravenspoint Commented Mar 19 at 14:03
• 1 added a toy example as requested – SudBstudying Commented Mar 19 at 15:47
• Thank you for the example, I will use it going forward. – ravenspoint Commented Mar 19 at 16:24

2 Answers 2

Here is how I would approach formulating your problem as an integer linear programming problem.

The decision variables are the weight assigned to each plate. wxpy is 1 if weight x is assigned to plate y, 0 if weight x is assigned elsewhere or not assigned.

The objective function coefficients are the difference between the weight assigned to each plate and the weight required by that plate multiplied by the penalty. This is where the difficulty arises! The penalty is not linear - if the weight is insufficient then there is a finite penalty, but any extra weight incurs zero penalty. Also the 'base penalty' adds another non-linear snag.

My solution is that we force the objective function to be linear by optimizing the number of plates fully pressed down, with the assumption that this will give the optimal assignments for those plates that ARE fully pressed down. Then we reduce the problem to focus on the partially pressed plates, ignore the base penalties, and optimize the remaining linear penalty values.

I believe that this will work correctly. To be sure, I would like to test on a couple of concrete example problems. First a toy problem ( say two plates and three weights ) so I can check that I fully understand your problem description. Second a full scale 'real' problem for testing.

On proof reading this answer, I realize that I have used some terminology that may well be unfamiliar if you have not done any linear programming work. Please google or take a look at https://en.wikipedia./wiki/Linear_programming

So, let's start by formulating the first pass problem, where we only look at whether or not each plate is fully pushed down.

Objective function:

maximize ( sum over all y ) fy  ( where fy = 1 if plate y fully pressed )

Constraint: a weight can only be assigned to one plate. So we need a constraint for each weight, like this:

(sum over all y ) wxpy <= 1

Constraint: each plate needs weight greater than minimum. So we need a constraint for each plate, like this:

( sum over all x ) wxpy >= my ( where my is the minimum weight for plate y )

If you would like to follow along as I work on this problem you can monitor my code repository for this work at https://codeberg./JamesBremner/PlatePresser. You are welcome to open issues for any problems or questions you have.

As an alternative to MIP and linearization of binary decision vars, applying a declarative approach to formulate such combinatorial problems with Clingo:

I hope, I got it right:
We want to minimize the total of the penalties, with a penalty defined as the (gap% + extra%) * base_penalty if a plate is not fully loaded.

Instance with the toy sample as a PoC:
note: penalty is scaled up by 100 to have % as integer

% Facts -------------
weight(1,2). weight(2,3). weight(3,4).
plate(1..2).
min_weight(1,4).    min_weight(2,10).
base_penalty(1,20). base_penalty(2,150).
extra_penalty(15).

% Rules -------------
{ assign(X,Y) : plate(Y) } 1 :- weight(X,_).
load(Y,L) :- plate(Y), L = #sum{ W,X : weight(X,W),assign(X,Y) }.
gap(Y,R) :- plate(Y), load(Y,L), min_weight(Y,M), L<M, R = (M-L)*100/M.
penalty(Y,T) :- gap(Y,R), base_penalty(Y,P), extra_penalty(C), T = (R+C)*P.

% Otimization --------
#minimize { T@1,Y : penalty(Y,T) }.

% Output -------------
#show penalty/2.
#show gap/2.

Output: (copy and paste the code to run it online)

clingo version 5.7.2 (6bd7584d)
Reading from stdin
Solving...
Answer: 1
gap(1,100) gap(2,100) penalty(1,2300) penalty(2,17250)
Optimization: 19550
Answer: 2
gap(1,50) gap(2,100) penalty(1,1300) penalty(2,17250)
Optimization: 18550
Answer: 3
gap(1,100) gap(2,80) penalty(1,2300) penalty(2,14250)
Optimization: 16550
Answer: 4
gap(1,25) gap(2,80) penalty(1,800) penalty(2,14250)
Optimization: 15050
Answer: 5
gap(1,100) gap(2,50) penalty(1,2300) penalty(2,9750)
Optimization: 12050
Answer: 6
gap(2,50) penalty(2,9750)
Optimization: 9750
Answer: 7
gap(1,100) gap(2,30) penalty(1,2300) penalty(2,6750)
Optimization: 9050
Answer: 8
gap(1,50) gap(2,30) penalty(1,1300) penalty(2,6750)
Optimization: 8050
Answer: 9
gap(1,100) gap(2,10) penalty(1,2300) penalty(2,3750)
Optimization: 6050
OPTIMUM FOUND

Models       : 9
  Optimum    : yes
Optimization : 6050
Calls        : 1
Time         : 0.064s (Solving: 0.01s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Edit:

To answer OP’s question, the problem reminds me of a multi knapsack problem, but not exactly due to the penalties.

So, besides the MIP approach (with some linearization efforts) as proposed by @ravenspoint[*], I do find the formulation of such problems easier with Constraint Programming, such as CP-SAT (where Boolean decision vars and conditional constraints are supported).

And it feels even more concise and ‘elegant’ with Answer Set Programming, as I tried to demonstrate with the Clingo code above.

[*] it’s also worth to mention: he uses his own implementation of Simplex that handles integer variables with heuristics (see the comments below his answer)