Numerous real-life decision-making processes involve solving a combinatorial optimization problem with uncertain input that can be estimated from historic data. There is a growing interest in decision-focused learning methods, where the loss function used for learning to predict the uncertain input uses the outcome of solving the combinatorial problem over a set of predictions. Different surrogate loss functions have been identified, often using a continuous approximation of the combinatorial problem. However, a key bottleneck is that to compute the loss, one has to solve the combinatorial optimisation problem for each training instance in each epoch, which is computationally expensive even in the case of continuous approximations. We propose a different solver-agnostic method for decision-focused learning, namely by considering a pool of feasible solutions as a discrete approximation of the full combinatorial problem. Solving is now trivial through a single pass over the solution pool. We design several variants of a noise-contrastive loss over the solution pool, which we substantiate theoretically and empirically. Furthermore, we show that by dynamically re-solving only a fraction of the training instances each epoch, our method performs on par with the state of the art, whilst drastically reducing the time spent solving, hence increasing the feasibility of predict-and-optimize for larger problems.

The study of random constraint satisfaction problems (CSPs) has received tremendous ideas from combinatorics, computer science and statistical physics. Random CSPs contain a large set of variables which interact through a large set of constraints, where each variable ranges over a domain and a configuration (solution) to all the variables should satisfy all of the constraints. A fundamental question in the study of random CSPs is the average-case computational complexity of solving ensembles of CSPs. Great amount of theoretical and algorithmic work has been devoted to establish and locate the satisfiability threshold, and studies show that complexity attains the maximum at the SAT-UNSAT transition. Many of the studied CSP models (such as random k-SAT, graph coloring) have fixed domain size, constraint length, and the number of constraints is linear compared with the number of variables. In recent years, a lot of attention has been paid to the study of CSPs with growing domains or constraint length ([13, 7, 4, 5]).

Combinatorial optimization problems are notoriously challenging for neural networks, especially in the absence of labeled instances. This work proposes an unsupervised learning framework for CO problems on graphs that can provide integral solutions of certified quality. Inspired by Erdos' probabilistic method, we use a neural network to parametrize a probability distribution over sets. Crucially, we show that when the network is optimized w.r.t. a suitably chosen loss, the learned distribution contains, with controlled probability, a low-cost integral solution that obeys the constraints of the combinatorial problem. The probabilistic proof of existence is then derandomized to decode the desired solutions. We demonstrate the efficacy of this approach to obtain valid solutions to the maximum clique problem and to perform local graph clustering. Our method achieves competitive results on both real datasets and synthetic hard instances.

We propose a novel non-randomized anytime orienteering algorithm for finding k-optimal goals that maximize reward on a specialized graph with budget constraints. This specialized graph represents a real-world scenario which is analogous to an orienteering problem of finding k-most optimal goal states.

Temporal planning offers numerous advantages when based on an expressive representation. Timelines have been known to provide the required expressiveness but at the cost of search efficiency. We propose here a temporal planner, called FAPE, which supports many of the expressive temporal features of the ANML modeling language without loosing efficiency. FAPE's representation coherently integrates flexible timelines with hierarchical refinement methods that can provide efficient control knowledge. A novel reachability analysis technique is proposed and used to develop causal networks to constrain the search space. It is employed for the design of informed heuristics, inference methods and efficient search strategies. Experimental results on common benchmarks in the field permit to assess the components and search strategies of FAPE, and to compare it to IPC planners. The results show the proposed approach to be competitive with less expressive planners and often superior when hierarchical control knowledge is provided. FAPE, a freely available system, provides other features, not covered here, such as the integration of planning with acting, and the handling of sensing actions in partially observable environments.

We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NEXPTIME-completeness and extend this result to monadic disjunctive Datalog and to OMQs.

Many real-world physical control systems are required to satisfy constraints upon deployment. Furthermore, real-world systems are often subject to effects such as non-stationarity, wear-and-tear, uncalibrated sensors and so on. Such effects effectively perturb the system dynamics and can cause a policy trained successfully in one domain to perform poorly when deployed to a perturbed version of the same domain. This can affect a policy's ability to maximize future rewards as well as the extent to which it satisfies constraints. We refer to this as constrained model misspecification. We present an algorithm with theoretical guarantees that mitigates this form of misspecification, and showcase its performance in multiple Mujoco tasks from the Real World Reinforcement Learning (RWRL) suite.

A robot understands its world through the raw information it senses from its surroundings. This raw information is not suitable as a shared representation between the robot and its user. A semantic map, containing high-level information that both the robot and user understand, is better suited to be a shared representation. We use the semantic map as the user-facing interface on our fleet of floor-cleaning robots. Jitter in the robot's sensed raw map, dynamic objects in the environment, and exploration of new space by the robot are common challenges for robots. Solving these challenges effectively in the context of semantic maps is key to enabling semantic maps for lifelong mapping. First, as a robot senses new changes and alters its raw map in successive runs, the semantics must be updated appropriately. We update the map using a spatial transfer of semantics. Second, it is important to keep semantics and their relative constraints consistent even in the presence of dynamic objects. Inconsistencies are automatically determined and resolved through the introduction of a map layer of meta-semantics. Finally, a discovery phase allows the semantic map to be updated with new semantics whenever the robot uncovers new information. Deployed commercially on thousands of floor-cleaning robots in real homes, our user-facing semantic maps provide a intuitive user experience through a lifelong mapping robot.

Single cells continuously experience and react to mechanical challenges in three-dimensional tissues. Spatial constraints in dense tissues, physical activity, and injury all impose changes in cell shape. How cells can measure shape deformations to ensure correct tissue development and homeostasis remains largely unknown (see the Perspective by Shen and Niethammer). Working independently, Venturini et al. and Lomakin et al. now show that the nucleus can act as an intracellular ruler to measure cellular shape variations. The nuclear envelope provides a gauge of cell deformation and activates a mechanotransduction pathway that controls actomyosin contractility and migration plasticity. The cell nucleus thereby allows cells to adapt their behavior to the local tissue microenvironment. Science , this issue p. [eaba2644][1], p. [eaba2894][2]; see also p. [295][3] ### INTRODUCTION The human body is a crowded place. This crowding is even more acute when the regulation of cell growth and proliferation fails during the formation of a tumor. Dealing with the lack of space in crowded environments presents cells with a challenge. This is especially true for immune cells, whose task is to patrol tissues, causing them to experience both acute and sustained deformation as they move. Although changes in tissue crowding and associated cell shape alterations have been known by pathologists to be key diagnostic traits of late-stage tumors since the 19th century, the impact of these changes on the biology of cancer and immune cells remains unclear. Moreover, it is not known whether cells can detect and adaptively respond to deformations in densely packed spaces. ### RATIONALE To test the hypothesis that cells possess an ability to detect and respond to environmentally induced changes in their shape, we fabricated artificial microenvironments that mimic the conditions experienced by tumor and immune cells in a crowded tissue. By combining dynamic confinement, force measurements, and live cell imaging, we were able to quantify cell responses to precisely controlled physical perturbations of their shape. ### RESULTS Our results show that, although cells are surprisingly resistant to compressive forces, they monitor their own shape and develop an active contractile response when deformed below a specific height. Notably, we find that this is achieved by cells monitoring the deformation of their largest internal compartment: the nucleus. We establish that the nucleus provides cells with a precise measure of the extent of their deformation. Once cell compression exceeds the size of the nucleus, it causes the bounding nuclear envelope (NE) to unfold and stretch. The onset of the contractile response occurs when the NE reaches a fully unfolded state. This transition in the mechanical state of the NE and its membranes permits calcium release from internal membrane stores and activates the calcium-dependent phospholipase cPLA2, an enzyme known to operate as a molecular sensor of nuclear membrane tension and a critical regulator of signaling and metabolism. Activated cPLA2 catalyzes the formation of arachidonic acid, an omega-6 fatty acid that, among other processes, potentiates the adenosine triphosphatase activity of myosin II. This induces contractility of the actomyosin cortex, which produces pushing forces to resist physical compression and to rapidly squeeze the cell out of its compressive microenvironment in an “evasion reflex” mechanism. ### CONCLUSION Although the nucleus has traditionally been considered a passive storehouse for genetic material, our work identifies it as an active compartment that rapidly convers mechanical inputs into signaling outputs, with a critical role of its envelope in this sensing function. The nucleus is able to detect environmentally imposed compression and respond to it by generating a signal that is used to change cell behaviors. This phenomenon plays a critical role in ensuring that cells, such as the immune cells within a tumor, can adapt, survive, and efficiently move through a crowded and mechanically heterogeneous microenvironment. Characterizing the full spectrum of signals triggered by nuclear compression has the potential to elucidate mechanisms underlying signaling, epigenetic, and metabolic adaptations of cells to their mechanoenvironment and is thus an exciting avenue for future research. ![Figure][4] The nuclear ruler and its contribution to the “life cycle” of a confined cell. (1) Cell confinement below resting nucleus size, leading to nuclear deformation and to unfolding, and stretching of the nuclear envelope. (2) Nuclear membrane tension increase, which triggers calcium release, cPLA2 activation, and arachidonic acid (ARA) production. (3) Actomyosin force ( F ) generation. (4) Increased cell migratory capacity and escape from confinement. The microscopic environment inside a metazoan organism is highly crowded. Whether individual cells can tailor their behavior to the limited space remains unclear. In this study, we found that cells measure the degree of spatial confinement by using their largest and stiffest organelle, the nucleus. Cell confinement below a resting nucleus size deforms the nucleus, which expands and stretches its envelope. This activates signaling to the actomyosin cortex via nuclear envelope stretch-sensitive proteins, up-regulating cell contractility. We established that the tailored contractile response constitutes a nuclear ruler–based signaling pathway involved in migratory cell behaviors. Cells rely on the nuclear ruler to modulate the motive force that enables their passage through restrictive pores in complex three-dimensional environments, a process relevant to cancer cell invasion, immune responses, and embryonic development. [1]: /lookup/doi/10.1126/science.aba2644 [2]: /lookup/doi/10.1126/science.aba2894 [3]: /lookup/doi/10.1126/science.abe3881 [4]: pending:yes

Recent advancements in procedural content generation via machine learning enable the generation of video-game levels that are aesthetically similar to human-authored examples. However, the generated levels are often unplayable without additional editing. We propose a generate-then-repair framework for automatic generation of playable levels adhering to specific styles. The framework constructs levels using a generative adversarial network (GAN) trained with human-authored examples and repairs them using a mixed-integer linear program (MIP) with playability constraints. A key component of the framework is computing minimum cost edits between the GAN generated level and the solution of the MIP solver, which we cast as a minimum cost network flow problem. Results show that the proposed framework generates a diverse range of playable levels, that capture the spatial relationships between objects exhibited in the human-authored levels.