Finding Probably Approximate Optimal Solutions by Training to Estimate the Optimal Values of Subproblems
This work addresses optimization challenges in binary variable domains, presenting an incremental approach by introducing a novel training method for value estimation.
The paper tackles the problem of maximizing a real-valued function of binary variables by developing a solver that estimates optimal values of subproblems, using a loss function based on expected total deviation from optimality conditions without calculating policy values or relying on solved instances.
The paper is about developing a solver for maximizing a real-valued function of binary variables. The solver relies on an algorithm that estimates the optimal objective-function value of instances from the underlying distribution of objectives and their respective sub-instances. The training of the estimator is based on an inequality that facilitates the use of the expected total deviation from optimality conditions as a loss function rather than the objective-function itself. Thus, it does not calculate values of policies, nor does it rely on solved instances.