One of the possible ways to solve such problem is to use integer programming. The idea is to transform your problem to a set of linear constraints on integer variables.
For example, saying that a roll has a length of of 150m can be translated into a constraint that you cannot cut more than 150m out of the roll. So if the number of Marker1 you cut on this roll is $m_1$, the number of Marker2 you cut on this roll is $m_2$, and so on, the constraint will be
$$10.5\times m_1 + 11\times m_2 + 5.2\times m_3 + 6.1\times m_4 + 2\times m_5 + leftover = 150$$
Here, I added a variable $leftover$ to change the constraint to an equality. This way, it's easy to know how much you have left of each roll. Since we want to manipulate only integers, you can multiply the equation by 10.
Now, we also need the constraints about the number of markers we want to cut. This follow the same principle: the sum of Marker1 we get from each roll should be equal to 100.
As a final constraint, all the variables we use here should be positive integers.
Once we have all the necessary constraints, we need a function to optimize the system. This is the metric that will tell you the quality of an answer. Since the amount of leftover will be always the same if you cut the same number of markers, we want to know the amount of leftover that cannot be reused to cut additional markers. To do this, we will change slightly the constraints about the number of markers to cut: instead of cutting exactly the required number of markers, we will cut at least the required number of markers. Then, the objective will be to reduce the amount of leftover.
Now, for the application, the best way is still to use a computer. There are a lot of libraries to solve integer programming problems since it's something quite common. For this exemple, I used Google Optimization Tools or-tools mostly because I wanted to try it. To be honest, I never used any tool for this before, so I cannot give recommendation about which tool is the best. So I wrote this small python script:
"""Linear optimization example"""
from __future__ import print_function
from ortools.linear_solver import pywraplp
def main():
# Instantiate a Glop solver, naming it SolveSimpleSystem.
solver = pywraplp.Solver('SolveSimpleSystem',
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
markers = [
(100, 105),
(80, 110),
(20, 52),
(20, 61),
(6, 20)
]
rolls = [
(2, 1500),
(4, 1200),
(12, 1000),
(5, 500),
(3, 200)
]
variables = []
left_variables = []
# Constraints for the size of the rolls
for roll_num, roll_size in rolls:
for roll_index in range(0, roll_num):
roll_variables = []
constraint = solver.Constraint(roll_size, roll_size)
for _, marker_size in markers:
variable = solver.IntVar(
0, solver.infinity(),
'r%d_%d m%d' % (roll_size, roll_index, marker_size))
constraint.SetCoefficient(variable, marker_size)
roll_variables.append(variable)
left = solver.IntVar(0, solver.infinity(),
'r%d_%d left' % (roll_size, roll_index))
constraint.SetCoefficient(left, 1)
left_variables.append(left)
variables.append(roll_variables)
# Constraints for the number of markers
for marker_index, (marker_num, _) in enumerate(markers):
constraint = solver.Constraint(marker_num, solver.infinity())
for roll_variables in variables:
constraint.SetCoefficient(roll_variables[marker_index], 1)
# Objective to maximize the size of leftover
objective = solver.Objective()
for left_variable in left_variables:
objective.SetCoefficient(left_variable, 1)
objective.SetMinimization()
# Solve the system
solver.set_time_limit(60*1000) # 1 min
status = solver.Solve()
status_dict = {
pywraplp.Solver.OPTIMAL: 'Optimal',
pywraplp.Solver.FEASIBLE: 'Feasible',
pywraplp.Solver.INFEASIBLE: 'Infeasible',
pywraplp.Solver.UNBOUNDED: 'Unbounded',
pywraplp.Solver.ABNORMAL: 'Abnormal',
pywraplp.Solver.NOT_SOLVED: 'Not solved'
}
print('Status =', status_dict[status])
assert status in (pywraplp.Solver.OPTIMAL, pywraplp.Solver.FEASIBLE)
assert solver.VerifySolution(1e-7, True)
print('Number of variables =', solver.NumVariables())
print('Number of constraints =', solver.NumConstraints())
# The optimal solution
opt_solution = sum(
left_variable.solution_value() for left_variable in left_variables)
print('Found solution =', opt_solution)
# Number of additionnal markers
for marker_index, (marker_target, marker_size) in enumerate(markers):
num_marker = sum(roll_variables[marker_index].solution_value()
for roll_variables in variables)
print('Marker %d has %d more.' % (marker_size, num_marker - marker_target))
# Detail of cut
for roll_variables in variables:
for variable in roll_variables:
if variable.solution_value() > 0:
print('%s = %d' % (variable.name(), variable.solution_value()))
if __name__ == '__main__':
main()
The result which has not been proven to be optimal (but might as well be) is the following:
- 14.8m of leftover
- 1 more Marker3
- 51 more Marker5
The full detail of the cut follows. r1500_0 m105 = 7 means that we should cut 7 Marker of size 10.5m from the first roll of size 150m.
r1500_0 m105 = 7
r1500_0 m110 = 6
r1500_0 m61 = 1
r1500_0 m20 = 2
r1500_1 m105 = 11
r1500_1 m110 = 2
r1500_1 m61 = 2
r1200_0 m105 = 5
r1200_0 m110 = 5
r1200_0 m61 = 2
r1200_1 m105 = 1
r1200_1 m110 = 7
r1200_1 m61 = 5
r1200_1 m20 = 1
r1200_2 m105 = 6
r1200_2 m110 = 3
r1200_2 m20 = 12
r1200_3 m105 = 7
r1200_3 m52 = 3
r1200_3 m61 = 3
r1200_3 m20 = 6
r1000_0 m105 = 8
r1000_0 m110 = 1
r1000_0 m20 = 2
r1000_1 m110 = 7
r1000_1 m52 = 4
r1000_1 m20 = 1
r1000_2 m110 = 7
r1000_2 m52 = 4
r1000_2 m20 = 1
r1000_3 m105 = 7
r1000_3 m52 = 1
r1000_3 m61 = 3
r1000_3 m20 = 1
r1000_4 m105 = 8
r1000_4 m52 = 3
r1000_5 m105 = 8
r1000_5 m110 = 1
r1000_5 m20 = 2
r1000_6 m110 = 9
r1000_7 m105 = 9
r1000_7 m52 = 1
r1000_8 m105 = 9
r1000_8 m20 = 2
r1000_9 m110 = 7
r1000_9 m52 = 2
r1000_9 m61 = 1
r1000_9 m20 = 3
r1000_10 m105 = 2
r1000_10 m110 = 7
r1000_10 m20 = 1
r1000_11 m110 = 9
r500_0 m110 = 3
r500_0 m52 = 2
r500_0 m61 = 1
r500_1 m110 = 4
r500_1 m20 = 3
r500_2 m105 = 4
r500_2 m20 = 4
r500_3 m105 = 2
r500_3 m110 = 2
r500_3 m61 = 1
r500_4 m105 = 4
r500_4 m61 = 1
r200_0 m105 = 1
r200_0 m52 = 1
r200_0 m20 = 2
r200_1 m105 = 1
r200_1 m20 = 4
r200_2 m20 = 10
