The goal of this paper is to set a constraint programming framework to solve lot-sizing problems. More specifically, we consider a single-item lot-sizing problem with time-varying lower and upper bounds for production and inventory. The cost structure includes time-varying holding costs, unitary production costs and setup costs. We establish a new lower bound for this problem by using a subtle time decomposition. We formulate this NP-hard problem as a global constraint and show that bound consistency can be achieved in pseudo-polynomial time and when not including the costs, in polynomial time. We develop filtering rules based on existing dynamic programming algorithms, exploiting the above mentioned time decomposition for difficult instances. In a numerical study, we compare several formulations of the problem: mixed integer linear programming, constraint programming and dynamic programming. We show that our global constraint is able to find solutions, unlike the decomposed constraint programming model and that constraint programming can be competitive, in particular when adding combinatorial side constraints.

In this paper, we study a class of online optimization problems with long-term budget constraints where the objective functions are not necessarily concave (nor convex) but they instead satisfy the Diminishing Returns (DR) property. Specifically, a sequence of monotone DR-submodular objective functions $\{f_t(x)\}_{t=1}^T$ and monotone linear budget functions $\{\langle p_t,x \rangle \}_{t=1}^T$ arrive over time and assuming a total targeted budget $B_T$, the goal is to choose points $x_t$ at each time $t\in\{1,\dots,T\}$, without knowing $f_t$ and $p_t$ on that step, to achieve sub-linear regret bound while the total budget violation $\sum_{t=1}^T \langle p_t,x_t \rangle -B_T$ is sub-linear as well. Prior work has shown that achieving sub-linear regret is impossible if the budget functions are chosen adversarially. Therefore, we modify the notion of regret by comparing the agent against a $(1-\frac{1}{e})$-approximation to the best fixed decision in hindsight which satisfies the budget constraint proportionally over any window of length $W$. We propose the Online Saddle Point Hybrid Gradient (OSPHG) algorithm to solve this class of online problems. For $W=T$, we recover the aforementioned impossibility result. However, when $W=o(T)$, we show that it is possible to obtain sub-linear bounds for both the $(1-\frac{1}{e})$-regret and the total budget violation.

Many of the famous single-player games, commonly called puzzles, can be shown to be NP-Complete. Indeed, this class of complexity contains hundreds of puzzles, since people particularly appreciate completing an intractable puzzle, such as Sudoku, but also enjoy the ability to check their solution easily once it's done. For this reason, using constraint programming is naturally suited to solve them. In this paper, we focus on logic puzzles described in the Ludii general game system and we propose using the XCSP formalism in order to solve them with any CSP solver.

Quantified Boolean Formulas (QBFs) can be used to succinctly encode problems from domains such as formal verification, planning, and synthesis. One of the main approaches to QBF solving is Quantified Conflict Driven Clause Learning (QCDCL). By default, QCDCL assigns variables in the order of their appearance in the quantifier prefix so as to account for dependencies among variables. Dependency schemes can be used to relax this restriction and exploit independence among variables in certain cases, but only at the cost of nontrivial interferences with the proof system underlying QCDCL. We introduce dependency learning, a new technique for exploiting variable independence within QCDCL that allows solvers to learn variable dependencies on the fly. The resulting version of QCDCL enjoys improved propagation and increased flexibility in choosing variables for branching while retaining ordinary (long-distance) Q-resolution as its underlying proof system. We show that dependency learning can achieve exponential speedups over ordinary QCDCL. Experiments on standard benchmark sets demonstrate the effectiveness of this technique.

Vehicle routing problems have been the focus of extensive research over the past sixty years, driven by their economic importance and their theoretical interest. The diversity of applications has motivated the study of a myriad of problem variants with different attributes. In this article, we provide a brief survey of existing and emerging problem variants. Models are typically refined along three lines: considering more relevant objectives and performance metrics, integrating vehicle routing evaluations with other tactical decisions, and capturing fine-grained yet essential aspects of modern supply chains. We organize the main problem attributes within this structured framework. We discuss recent research directions and pinpoint current shortcomings, recent successes, and emerging challenges.

In this article we demonstrate how to solve a variety of problems and puzzles using the built-in SAT solver of the computer algebra system Maple. Once the problems have been encoded into Boolean logic, solutions can be found (or shown to not exist) automatically, without the need to implement any search algorithm. In particular, we describe how to solve the $n$-queens problem, how to generate and solve Sudoku puzzles, how to solve logic puzzles like the Einstein riddle, how to solve the 15-puzzle, how to solve the maximum clique problem, and finding Graeco-Latin squares.

This paper presents a two-step generative approach for creating While research on level generation focuses on level generators dungeons in the rogue-like puzzle game MiniDungeons 2. Generation based on stochastic search [14], constraint solving [11, 12], or machine is split into two steps, initially producing the architectural learning [13], level generation in published games is mostly layout of the level as its walls and floor tiles, and then furnishing it carried out via constructive algorithms. Unlike generate-and-test with game objects representing the player's start and goal position, processes, constructive generators do not evaluate and regenerate challenges and rewards. Three layout creators and three furnishers output; for example, cellular automata and grammars can be used are introduced in this paper, which can be combined in different for constructive generation, as well as more freeform approaches ways in the two-step generative process for producing diverse dungeons such as diggers [10]. Such generators are computationally lightweight levels. Layout creators generate the floors and walls of a level, since they do not evaluate their generated output. This while furnishers populate it with monsters, traps, and treasures.

Integer programming (IP) is a general optimization framework widely applicable to a variety of unstructured and structured problems arising in, e.g., scheduling, production planning, and graph optimization. As IP models many provably hard to solve problems, modern IP solvers rely on many heuristics. These heuristics are usually human-designed, and naturally prone to suboptimality. The goal of this work is to show that the performance of those solvers can be greatly enhanced using reinforcement learning (RL). In particular, we investigate a specific methodology for solving IPs, known as the Cutting Plane Method. This method is employed as a subroutine by all modern IP solvers. We present a deep RL formulation, network architecture, and algorithms for intelligent adaptive selection of cutting planes (aka cuts). Across a wide range of IP tasks, we show that the trained RL agent significantly outperforms human-designed heuristics, and effectively generalizes to 10X larger instances and across IP problem classes. The trained agent is also demonstrated to benefit the popular downstream application of cutting plane methods in Branch-and-Cut algorithm, which is the backbone of state-of-the-art commercial IP solvers.

Many signal processing algorithms break the target signal into overlapping segments (also called windows, or patches), process them separately, and then stitch them back into place to produce a unified output. At the overlaps, the final value of those samples that are estimated more than once needs to be decided in some way. Averaging, the simplest approach, tends to produce blurred results. Significant work has been devoted to this issue in recent years: several works explore the idea of a weighted average of the overlapped patches and/or pixels; a more recent approach is to promote agreement (consensus) between the patches at their intersections. This work investigates the case where consensus is imposed as a hard constraint on the restoration problem. This leads to a general framework applicable to all sorts of signals, problems, decomposition strategies, and featuring a number of theoretical and practical advantages over other similar methods. The framework itself consists of a general optimization problem and a simple and efficient \admm-based algorithm for solving it. We also show that the consensus step of the algorithm, which is the main bottleneck of similar methods, can be solved efficiently and easily for any arbitrary patch decomposition scheme. As an example of the potential of our framework, we propose a method for filling missing samples (inpainting) which can be applied to signals of any dimension, and show its effectiveness on audio, image and video signals.

We introduce Deep Reasoning Networks (DRNets), an end-to-end framework that combines deep learning with reasoning for solving complex tasks, typically in an unsupervised or weakly-supervised setting. DRNets exploit problem structure and prior knowledge by tightly combining logic and constraint reasoning with stochastic-gradient-based neural network optimization. We illustrate the power of DRNets on de-mixing overlapping hand-written Sudokus (Multi-MNIST-Sudoku) and on a substantially more complex task in scientific discovery that concerns inferring crystal structures of materials from X-ray diffraction data under thermodynamic rules (Crystal-Structure-Phase-Mapping). At a high level, DRNets encode a structured latent space of the input data, which is constrained to adhere to prior knowledge by a reasoning module. The structured latent encoding is used by a generative decoder to generate the targeted output. Finally, an overall objective combines responses from the generative decoder (thinking fast) and the reasoning module (thinking slow), which is optimized using constraint-aware stochastic gradient descent. We show how to encode different tasks as DRNets and demonstrate DRNets' effectiveness with detailed experiments: DRNets significantly outperform the state of the art and experts' capabilities on Crystal-Structure-Phase-Mapping, recovering more precise and physically meaningful crystal structures. On Multi-MNIST-Sudoku, DRNets perfectly recovered the mixed Sudokus' digits, with 100% digit accuracy, outperforming the supervised state-of-the-art MNIST de-mixing models. Finally, as a proof of concept, we also show how DRNets can solve standard combinatorial problems -- 9-by-9 Sudoku puzzles and Boolean satisfiability problems (SAT), outperforming other specialized deep learning models. DRNets are general and can be adapted and expanded to tackle other tasks.