Scholarlink

<p>Combinatorial optimization problems represent a critical class of challenges in the field of operations research and computer science. These problems involve making optimal choices from a finite set of possibilities, subject to specific constraints, with the aim of optimizing a certain objective function. Combinatorial optimization encompasses a diverse array of applications, ranging from resource allocation, scheduling, and network design to logistics, facility location, and circuit design. However, most combinatorial optimization problems are <b>NP-hard</b>, which necessitates the development of sophisticated algorithms and heuristics to find near-optimal solutions efficiently. Researchers in this area continuously strive to devise innovative approaches, such as integer programming, dynamic programming, and metaheuristics, to address these challenges effectively. This paper investigates various <b>NP-hard</b> optimization problems, such as MAXCUT, MAXNAE2SAT, Subset Sum, and 0-1 Knapsack problem, with a focus on deriving exact solutions. We apply the framework of dataless neural networks to derive differentiable functions for each of these problems. Building on recent insights that a single differentiable function within a dataless neural network can solve the Maximum Independent Set problem, we adapt this methodology to address a broader array of combinatorial optimization problems. Additionally, we provide a thorough validation of the correctness of our derived functions. To demonstrate practical applicability, we implement the proposed MAXNAE2SAT dNN and extend it to capture MAXNAE3SAT through a principled modification of the objective function. The resulting solver requires no training data or hyperparameter tuning. We empirically evaluate the implementation on randomly generated instances and compare its performance against state-of-the-art combinatorial optimization solvers, including CP-SAT and Gurobi. Experimental results show that dNNs achieve competitive approximate solutions with sub-millisecond runtimes and substantially lower memory consumption, highlighting their potential as memory-efficient solvers for large-scale combinatorial optimization.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Differential techniques for addressing SAT variants and related problems*

  • 期刊论文

  • 发表日期：

    2026年3月26日

查看全文
  • Sangram K. Jena,
  • K. Subramani,
  • Andrew Gautier,
  • Piotr Wojciechowski,
  • Alvaro Velasquez

摘要

Combinatorial optimization problems represent a critical class of challenges in the field of operations research and computer science. These problems involve making optimal choices from a finite set of possibilities, subject to specific constraints, with the aim of optimizing a certain objective function. Combinatorial optimization encompasses a diverse array of applications, ranging from resource allocation, scheduling, and network design to logistics, facility location, and circuit design. However, most combinatorial optimization problems are NP-hard, which necessitates the development of sophisticated algorithms and heuristics to find near-optimal solutions efficiently. Researchers in this area continuously strive to devise innovative approaches, such as integer programming, dynamic programming, and metaheuristics, to address these challenges effectively. This paper investigates various NP-hard optimization problems, such as MAXCUT, MAXNAE2SAT, Subset Sum, and 0-1 Knapsack problem, with a focus on deriving exact solutions. We apply the framework of dataless neural networks to derive differentiable functions for each of these problems. Building on recent insights that a single differentiable function within a dataless neural network can solve the Maximum Independent Set problem, we adapt this methodology to address a broader array of combinatorial optimization problems. Additionally, we provide a thorough validation of the correctness of our derived functions. To demonstrate practical applicability, we implement the proposed MAXNAE2SAT dNN and extend it to capture MAXNAE3SAT through a principled modification of the objective function. The resulting solver requires no training data or hyperparameter tuning. We empirically evaluate the implementation on randomly generated instances and compare its performance against state-of-the-art combinatorial optimization solvers, including CP-SAT and Gurobi. Experimental results show that dNNs achieve competitive approximate solutions with sub-millisecond runtimes and substantially lower memory consumption, highlighting their potential as memory-efficient solvers for large-scale combinatorial optimization.