Paper Rolls And Sizes.

To address the problem of cutting paper rolls into different sizes efficiently, follow these steps:

### 1. **Problem Definition**

- **Original Roll Size**: E.g., 100 units (width/length).

- **Required Cuts**: Sizes and quantities (e.g., 30 units ×10, 20 units ×15, 40 units ×5).

- **Objective**: Minimize the number of rolls used (or total waste).

### 2. **Generate Cutting Patterns**

A cutting pattern is a combination of required sizes that fits into the original roll.

**Example Patterns for 100-unit roll**:

- **Pattern 1**: 2×40 + 1×20 (waste = 0).

- **Pattern 2**: 3×30 + 1×10 (waste = 10).

- **Pattern 3**: 5×20 (waste = 0).

Use combinatorial methods or algorithms to generate all feasible patterns.

### 3. **Formulate an Optimization Model**

**Variables**:

\( x_j \) = Number of times pattern \( j \) is used.

**Objective**:

Minimize total rolls:

\[

\text{Minimize } \sum_{j} x_j

\]

**Constraints**:

For each size \( i \), total produced ≥ demand:

\[

\sum_{j} (a_{ij} \cdot x_j) \geq d_i \quad \forall i

\]

where \( a_{ij} \) = number of size \( i \) in pattern \( j \), and \( d_i \) = demand for size \( i \).

### 4. **Solve the Model**

- **Exact Methods**: Use Integer Linear Programming (ILP) solvers (e.g., Gurobi, CPLEX) for small problems.

- **Heuristics**: For larger problems, use:

- **First Fit Decreasing (FFD)**: Prioritize larger cuts to minimize gaps.

- **Column Generation**: Iteratively generate efficient patterns without full enumeration.

### 5. **Example Solution**

For demands: 10×30, 15×20, 5×40 (original roll = 100):

- **Optimal Patterns**:

- 2×40 + 1×20 (used 2 times → 4×40, 2×20).

- 1×40 + 3×20 (used 1 time → 1×40, 3×20).

- 5×20 (used 2 times → 10×20).

- 3×30 (used 4 times → 12×30).

- **Total Rolls**: 9 (with 2 units of overproduction for size 30).

### 6. **Practical Tools**

- **Small Problems**: Excel Solver.

- **Larger Problems**: Python libraries (PuLP, OR-Tools) or specialized software.

### Key Considerations

- **Overproduction**: Decide if excess cuts are allowed (reduces waste but increases inventory).

- **Complexity**: Exact solutions are NP-hard; use heuristics for scalability.

By systematically generating patterns and optimizing their use, you can minimize material waste and costs effectively.