For example: "Exact Solution Techniques for Two-dimensional Cutting and Packing"

An exact solution is a solution that satisfies all the constraints and optimality conditions of a problem, while an optimal solution is a solution that minimizes (or maximizes) the objective function of a problem. An exact solution is always optimal, but an optimal solution may not be exact if it is obtained by approximation or heuristic methods.

For example, in the paper "Exact Solution Techniques for Two-dimensional Cutting and Packing", the authors consider four main problems: finding a packing with minimum height, packing the items into the minimum number of bins, finding a packing of maximum value, and determining the existence of a feasible packing. They survey the main formulations and solution methods for these problems, where both items and bins are rectangles. They focus on exact methods and relaxations, which are techniques that guarantee to find an exact solution or prove its nonexistence.

A relaxation is a modification of the original problem that makes it easier to solve, usually by removing some constraints or changing the objective function. A relaxation provides a lower (or upper) bound on the optimal value of the original problem, which can be used to prune the search space or guide the search process. A relaxation is exact if it coincides with the original problem.

Some examples of relaxations for two-dimensional cutting and packing problems are: linear programming relaxations, which replace integer variables with continuous ones; knapsack relaxations, which ignore some dimensions or constraints; and geometric relaxations, which use geometric properties to simplify the problem.

(1) Exact solution techniques for two-dimensional cutting and packing. https://www.sciencedirect.com/science/article/pii/S0377221720306111.

Lyudmil Antonov Thank you for your detailed answer!

I would like to clarify the question. Maybe you know the general definition of an exact solution that is different from optimal or extreme? Why did Lagrange, Euler or L.V. Kantorovich use the term relaxation and not exact solution?

These concepts are fundamental in many fields, including operations research, computer science, and mathematical optimization. So their definitions can vary depending on the field they are used in. Some general characteristics are the following:

• Exact solutions are particularly important when precision is crucial. They satisfy all constraints and optimality conditions of a problem. However, finding exact solutions can be computationally expensive or even impossible for complex problems.
• Optimal solutions are solutions that minimize or maximize the objective function of a problem. They may not be exact if they are obtained by approximation or heuristic methods, which are often used for complex problems where finding an exact solution is impractical.
• Relaxations are simplified versions of the original problem that are easier to solve. They provide bounds on the optimal value of the original problem, which can be used to guide the search process. Relaxations are a common technique in optimization and are used in methods like linear programming, integer programming, and cutting-plane methods.

The term “exact solution” generally refers to a solution that satisfies all the constraints and conditions of a problem without any approximation or simplification. It’s a solution that is derived directly from the problem’s governing equations.

On the other hand, an “optimal” or “extreme” solution refers to a solution that maximizes or minimizes a certain objective function, given a set of constraints. It’s not necessarily an exact solution, especially if the optimization problem is solved using approximate or heuristic methods.

The term “relaxation” is used in a different context. It refers to a technique where a difficult problem is replaced by a simpler one (the “relaxed” problem), making it easier to solve. The solution to the relaxed problem often serves as a good approximation to the original problem, or provides a bound on the optimal solution.

Lagrange, Euler, and L.V. Kantorovich, among others, used the term “relaxation” because they were often dealing with complex problems where finding an exact solution was difficult or impossible. By relaxing the problem, they could find solutions that, while not exact, were still useful and provided valuable insights into the problem.

For example, in the method of Lagrange multipliers (a technique for finding the local maxima and minima of a function subject to equality constraints), the original problem is “relaxed” by introducing additional variables (the Lagrange multipliers), which makes the problem easier to solve.

Similarly, L.V. Kantorovich, a mathematician who made significant contributions to the theory of optimal allocation of resources, used relaxation techniques to solve complex optimization problems.

In summary, the terms “exact solution”, “optimal solution”, and “relaxation” are used in different contexts and have different meanings.

Lyudmil Antonov, thank you!

I only know this definition (https://mathworld.wolfram.com/ExactSolution.html):

Exact Solution

As used in physics, the term "exact" generally refers to a solution that captures the entire physics and mathematics of a problem as opposed to one that is approximate, perturbative, etc. Exact solutions therefore need not be closed-form.