English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Finding tight bounds on the optimal solution is a critical element ofpractical solution methods for discrete optimization problems. In the lastdecade, decision diagrams (DDs) have brought a new perspective on obtainingupper and lower bounds that can be significantly better than classical boundingmechanisms, such as linear relaxations. It is well known that the quality ofthe bounds achieved through this flexible bounding method is highly reliant onthe ordering of variables chosen for building the diagram, and finding anordering that optimizes standard metrics is an NP-hard problem. In this paper,we propose an innovative and generic approach based on deep reinforcementlearning for obtaining an ordering for tightening the bounds obtained withrelaxed and restricted DDs. We apply the approach to both the MaximumIndependent Set Problem and the Maximum Cut Problem. Experimental results onsynthetic instances show that the deep reinforcement learning approach, byachieving tighter objective function bounds, generally outperforms orderingmethods commonly used in the literature when the distribution of instances isknown. To the best knowledge of the authors, this is the first paper to applymachine learning to directly improve relaxation bounds obtained bygeneral-purpose bounding mechanisms for combinatorial optimization problems.

Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning