Abstract: The simple assembly line balancing problem (SALBP) involves the determination of the assignment of elementary assembly operations to the workstations of the assembly line for the manufacture of a final product, with the objective of maximising assembly efficiency. In addition to its practicality, the SALBP can be considered as an extension of the bin packing problem (BPP) to account for the precedence relations between items. These constraints introduce an ordering component to the problem, which increases the complexity of SALBP resolution. However, previous studies indicated that precedence constraints do not play an important role in the capacity of state-of-the-art procedures to solve benchmark instances to optimality. In this study, we analysed the influences of different features of an SALBP instance on the performance of state-of-the-art solution methods for the abovementioned problem. First, we provide an alternative proof of complexity for the SALBP that uses precedence constraints to demonstrate its non-deterministic polynomial time (NP)-complete status, followed by a new set of benchmark instances directed towards an empirical analysis of the different features of SALBP instances. The experimental results revealed that the packing features of the SALBP are a major source of the perceived difficulty for any instance; however, precedence constraints play a role in the performance of these solution procedures. Specifically, the number of precedence constraints plays an important role in the results obtained from state-of-the-art methods. In addition to the analysis, certain issues that were identified in the publicly available implementations of the state-of-the-art method for resolving this problem were addressed in this study.

Abstract: We examine the unexplored effects on art markets of artist death (asset supply constraints), collectors' wealth (background risk) and forgery risk (risk of investment fraud), under short-sale constraints and risk aversion. Speculative bubbles emerge and have the form of an option strangle (a put option and a call option), in which strike prices are affected by art supply constraints and the association of the artworks' emotional value with both collectors' wealth and forgery, while the options' underlying asset is the stochastic heterogeneous beliefs of agents. We show that speculative bubbles increase with four elements: art supply constraints; a more negative correlation between collectors' wealth and the artworks' emotional value; a more positive relationship between forgery and the artworks' emotional value; and more heterogeneous beliefs. These four sources of speculation increase the expected turnover rate; however, they also augment the variance of speculative bubbles, which generates price discounts (i.e. risk premiums) for holding artworks. Consequently, the net impact of speculation is not necessarily increased art prices. This study not only contributes to the art market literature, but also to studies about speculative bubbles in other financial markets under heterogeneous beliefs, short-sale constraints and risk-averse investors, since we additionally consider the simultaneous effect of asset supply constraints, investors' background risk and the risk of investment fraud.

Abstract: We propose answer-set programs that specify and compute counterfactual interventions on entities that are input on a classification model. In relation to the outcome of the model, the resulting counterfactual entities serve as a basis for the definition and computation of causality-based explanation scores for the feature values in the entity under classification, namely responsibility scores. The approach and the programs can be applied with black-box models, and also with models that can be specified as logic programs, such as rule-based classifiers. The main focus of this study is on the specification and computation of best counterfactual entities, that is, those that lead to maximum responsibility scores. From them one can read off the explanations as maximum responsibility feature values in the original entity. We also extend the programs to bring into the picture semantic or domain knowledge. We show how the approach could be extended by means of probabilistic methods, and how the underlying probability distributions could be modified through the use of constraints. Several examples of programs written in the syntax of the DLV ASP-solver, and run with it, are shown.

Abstract: In this paper, we study the multi-asset Black-Scholes model from a structural point of view. For this, we interpret the multi-asset Black-Scholes equation as a multidimensional Schrodinger one particle equation. The analysis of the classical Hamiltonian and Lagrangian mechanics associated with this quantum model implies that, in this system, the canonical momentums cannot always be written in terms of the velocities. This feature is a typical characteristic of the constrained system that appears in the high-energy physics. To study this model in the proper form, one must apply Dirac's method for constrained systems. The results of the Dirac's analysis indicate that in the correlation parameters space of the multi assets model, there exists a surface (called the Kummer surface Sigma(K), where the determinant of the correlation matrix is null) on which the constraint number can vary. We study in detail the cases with N = 2 and N = 3 assets. For these cases, we calculate the propagator of the multi-asset Black-Scholes equation and show that inside the Kummer Sigma(K) surface the propagator is well defined, but outside Sigma(K) the propagator diverges and the option price is not well defined. On Sigma(K) the propagator is obtained as a constrained path integral and their form depends on which region of the Kummer surface the correlation parameters lie. Thus, the multi-asset Black-Scholes model is an example of a variable constrained dynamical system, and it is a new and beautiful property that had not been previously observed. (C) 2016 Elsevier B.V. All rights reserved.

Abstract: A dimension in a data warehouse (DW) is a set of elements connected by a hierarchical relationship. The elements are used to view summaries of data at different levels of abstraction. In order to support an efficient processing of such summaries, a dimension is usually required to satisfy different classes of integrity constraints. In scenarios where the constraints properly capture the semantics of the DW data, but they are not satisfied by the dimension, the problem of repairing (correcting) the dimension arises. In this paper, we study the problem of repairing a dimension in the context of two main classes of integrity constraints: strictness and covering constraints. We introduce the notion of minimal repair of a dimension: a new dimension that is consistent with respect to the set of integrity constraints, which is obtained by applying a minimal number of updates to the original dimension. We study the complexity of obtaining minimal repairs, and show how they can be characterized using Datalog programs with weak constraints under the stable model semantics. (c) 2012 Elsevier B.V. All rights reserved.

Abstract: The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand-side structures, the results of Dalmau, Languages and Programming, Springer, New York, 2007, pp. 279--290] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand-side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the kth level of the Sherali--Adams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognizing the tractable cases; the latter has an application in database theory.

Abstract: The stochastic volatility models used in the financial world are characterized, in the continuous-time case, by a set of two coupled stochastic differential equations for the underlying asset price S and volatility sigma. In addition, the correlations of the two Brownian movements that drive the stochastic dynamics are measured by the correlation parameter rho (-1 <= rho <= 1). This stochastic system is equivalent to the Fokker-Planck equation for the transition probability density of the random variables S and sigma. Solutions for the transition probability density of the Heston stochastic volatility model (Heston, 1993) were explored in Dragulescu and Yakovenko (2002), where the fundamental quantities such as the transition density itself, depend on rho in such a manner that these are divergent for the extreme limit rho = +/- 1. The same divergent behavior appears in Hagan et al. (2002), where the probability density of the SABR model was analyzed. In an option pricing context, the propagator of the bi-dimensional Black-Scholes equation was obtained in Lemmens et al. (2008) in terms of the path integrals, and in this case, the propagator diverges again for the extreme values rho = +/- 1. This paper shows that these similar divergent behaviors are due to a universal property of the stochastic volatility models in the continuum: all of them are second class constrained systems for the most extreme correlated limit rho = +/- 1. In this way, the stochastic dynamics of the rho = +/- 1 cases are different of the rho (1 <= rho <= 1) case, and it cannot be obtained as a continuous limit from the rho not equal +/- 1 regimen. This conclusion is achieved by considering the Fokker-Planck equation or the bi-dimensional Black-Scholes equation as a Euclidean quantum Schrodinger equation. Then, the analysis of the underlying classical mechanics of the quantum model, implies that stochastic volatility models at rho = +/- 1 correspond to a constrained system. To study the dynamics in an appropriate form, Dirac's method for constrained systems (Dirac, 1958, 1967) must be employed, and Dirac's analysis reveals that the constraints are second class. In order to obtain the transition probability density or the option price correctly, one must evaluate the propagator as a constrained Hamiltonian path-integral (Henneaux and Teitelboim, 1992), in a similar way to the high energy gauge theory models. In fact, for all stochastic volatility models, after integrating over momentum variables, one obtains an effective Euclidean Lagrangian path integral over the volatility alone. The role of the second class constraints is determining the underlying asset price S completely in terms of volatility, so it plays no role in the path integral. In order to examine the effect of the constraints on the dynamics for both extreme limits, the probability density function is evaluated by using semi-classical arguments, in an analogous manner to that developed in Hagan et al. (2002), for the SABR model. (C) 2014 Elsevier B.V. All rights reserved.

Abstract: In a recent article, a generic optimal control problem was studied from a physicist's point of view (Contreras et al. 2017). Through this optic, the Pontryagin equations are equivalent to the Hamilton equations of a classical constrained system. By quantizing this constrained system, using the right ordering of the operators, the corresponding quantum dynamics given by the Schrodinger equation is equivalent to that given by the Hamilton-Jacobi-Bellman equation of Bellman's theory. The conclusion drawn there were based on certain analogies between the equations of motion of both theories. In this paper, a closer and more detailed examination of the quantization problem is carried out, by considering three possible quantization procedures: right quantization, left quantization, and Feynman's path integral approach. The Bellman theory turns out to be the classical limit h -> 0 of these three different quantum theories. Also, the exact relation of the phase S(x, t) of the wave function Psi(x, t) = e(i/hS(x,t)) of the quantum theory with Bellman's cost function J(+)(x, t) is obtained. In fact, S(x, t) satisfies a 'conjugate' form of the Hamilton-Jacobi-Bellman equation, which implies that the cost functional J(+)(x, t) must necessarily satisfy the usual Hamilton-Jacobi-Bellman equation. Thus, the Bellman theory effectively corresponds to a quantum view of the optimal control problem. (C) 2018 Elsevier B.V. All rights reserved.

Abstract: Piscirickettsia salmonis is an intracellular bacterial fish pathogen that causes piscirickettsiosis, a disease with highly adverse impact in the Chilean salmon farming industry. The development of effective treatment and control methods for piscireckttsiosis is still a challenge. To meet it the number of studies on P. salmonis has grown in the last couple of years but many aspects of the pathogen's biology are still poorly understood. Studies on its metabolism are scarce and only recently a metabolic model for reference strain LF-89 was developed. We present a new genomescale model for P. salmonis LF-89 with more than twice as many genes as in the previous model and incorporating specific elements of the fish pathogen metabolism. Comparative analysis with models of different bacterial pathogens revealed a lower flexibility in P. salmonis metabolic network. Through constraint-based analysis, we determined essential metabolites required for its growth and showed that it can benefit from different carbon sources tested experimentally in new defined media. We also built an additional model for strain A1-15972, and together with an analysis of P. salmonis pangenome, we identified metabolic features that differentiate two main species clades. Both models constitute a knowledge-base for P. salmonis metabolism and can be used to guide the efficient culture of the pathogen and the identification of specific drug targets.

Abstract: We consider the problem of separating maximally violated inequalities for the precedence constrained knapsack problem. Though we consider maximally violated constraints in a very general way, special emphasis is placed on induced cover inequalities and induced clique inequalities. Our contributions include a new partial characterization of maximally violated inequalities, a new safe shrinking technique, and new insights on strengthening and lifting. This work follows on the work of Boyd (1993), Park and Park (1997), van de Leensel et al. (1999) and Boland et al. (2011). Computational experiments show that our new techniques and insights can be used to significantly improve the performance of cutting plane algorithms for this problem. (C) 2015 Elsevier B.V. All rights reserved.