Search

In this work, we propose a new Gaussian process (GP) regression framework that enforces the physical constraints in a probabilistic manner. Specifically, we focus on inequality and monotonicity constraints. This GP model is trained by the quantum-inspired Hamiltonian Monte Carlo (QHMC) algorithm, which is an efficient way to sample from a broad class of distributions by allowing a particle to have a random mass matrix with a probability distribution. Integrating the QHMC into the inequality and monotonicity constrained GP regression in the probabilistic sense, our approach enhances the accuracy and reduces the variance in the resulting GP model. Additionally, the probabilistic aspect of the method leads to reduced computational expenses and execution time. Further, we present an adaptive learning algorithm that guides the selection of constraint locations. The accuracy and efficiency of the method are demonstrated in estimating the hyperparameter of high-dimensional GP models under noisy conditions, reconstructing the sparsely observed state of a steady state heat transport problem, and learning a conservative tracer distribution from sparse tracer concentration measurements.

In this paper, we describe a branch-and-price algorithm for the personalized nurse scheduling problem. The variants that appear in the literature involve a large number of constraints that can be hard or soft, meaning that they can be violated at the price of a penalty. We capture the diversity of the constraints on individual schedules by seven generic constraints characterized by lower and upper bounds on a given quantity. The core of the column generation procedure is in the identification of individual schedules with minimum reduced cost. For this, we solve a shortest path problem with resource constraints (SPPRC) where several generic constraints are modeled as resource constraints. We then describe dominance rules adapted to the presence of both upper and lower bounds on the resources and leverage soft constraints to improve the dominance. We also describe several acceleration techniques for the solution of the SPPRC, and branching rules that fit the specificities of the problem. Our numerical experiments are based on the instances of three benchmarks of the literature including those of the two international nurse rostering competitions (INRC-I and INRC-II). Their objective is threefold: assess the dominance rules and the acceleration techniques, investigate the capacity of the algorithm to find provable optimal solutions of instances that are still open, and conduct a comparison with best published results. The most noticeable conclusion is that the improved solution of the SPPRC allows to solve optimally all the INRC-II instances where a four-week planning horizon is considered and 40% of the eight-week instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0019. [ABSTRACT FROM AUTHOR]

Semi-supervised clustering typically relies on both labeled and unlabeled data to guide the learning process towards the optimal data partition and to prevent falling into local minima. However, researchers' efforts made to improve existing semi-supervised clustering approaches are relatively scarce compared to the contributions made to enhance the state-of-the-art fully unsupervised clustering approaches. In this paper, we propose a novel semi-supervised deep clustering approach, named Soft Constrained Deep Clustering (SC-DEC), that aims to address the limitations exhibited by existing semi-supervised clustering approaches. Specifically, the proposed approach leverages a deep neural network architecture and generates fuzzy membership degrees that better reflect the true partition of the data. In particular, the proposed approach uses side-information and formulates it as a set of soft pairwise constraints to supervise the machine learning process. This supervision information is expressed using rather relaxed constraints named "should-link" constraints. Such constraints determine whether the pairs of data instances should be assigned to the same or different cluster(s). In fact, the clustering task was formulated as an optimization problem via the minimization of a novel objective function. Moreover, the proposed approach's performance was assessed via extensive experiments using benchmark datasets. Furthermore, the proposed approach was compared to relevant state-of-the-art clustering algorithms, and the obtained results demonstrate the impact of using minimal previous knowledge about the data in improving the overall clustering performance. [ABSTRACT FROM AUTHOR]

Decision systems for solving real-world combinatorial problems must be able to report infeasibility in such a way that users can understand the reasons behind it, and determine how to modify the problem to restore feasibility. Current methods mainly focus on reporting one or more subsets of the problem constraints that cause infeasibility. Methods that also show users how to restore feasibility tend to be less flexible and/or problem-dependent. We describe a problem-independent approach to feasibility restoration that combines existing techniques from the literature in novel ways to yield meaningful, useful, practical, and flexible user support. We evaluated the resulting framework on three real-world applications and conducted a qualitative expert user study with participants from different application domains. [ABSTRACT FROM AUTHOR]

Ecological networks such as plant–pollinator systems and food webs vary in space and time. This variability includes fluctuations in global properties such as the total number and intensity of interactions in the network but also in the number and intensity of local (i.e. node level) species interactions.Fluctuations of species' properties can significantly affect higher‐order network features, for example, robustness and nestedness, and should therefore be taken into account in null models for pattern detection and hypothesis testing.In ecological research, classical null models treat node‐level properties as 'hard' constraints that cannot fluctuate. Here, we review and synthesize a set of maximum‐entropy methods that allow for fluctuating ('soft') constraints, offering a new addition to the classical toolkit of the ecologist. We illustrate the methods with some practical examples, pointing to currently available open‐source computer codes. We clarify how this approach can be used by experimental ecologists to detect non‐random patterns with null models that not only rewire, but also redistribute interaction strengths by allowing fluctuations in the enforced constraints.Explicit modelling of interspecific heterogeneity through local (i.e. species level) fluctuations of topological and quantitative constraints offers a statistically robust and expanded (e.g. including weighted links) set of tools to understand the assembly and resilience of ecological networks. [ABSTRACT FROM AUTHOR]

Semi-supervised clustering typically relies on both labeled and unlabeled data to guide the learning process towards the optimal data partition and to prevent falling into local minima. However, researchers’ efforts made to improve existing semi-supervised clustering approaches are relatively scarce compared to the contributions made to enhance the state-of-the-art fully unsupervised clustering approaches. In this paper, we propose a novel semi-supervised deep clustering approach, named Soft Constrained Deep Clustering (SC-DEC), that aims to address the limitations exhibited by existing semi-supervised clustering approaches. Specifically, the proposed approach leverages a deep neural network architecture and generates fuzzy membership degrees that better reflect the true partition of the data. In particular, the proposed approach uses side-information and formulates it as a set of soft pairwise constraints to supervise the machine learning process. This supervision information is expressed using rather relaxed constraints named “should-link” constraints. Such constraints determine whether the pairs of data instances should be assigned to the same or different cluster(s). In fact, the clustering task was formulated as an optimization problem via the minimization of a novel objective function. Moreover, the proposed approach’s performance was assessed via extensive experiments using benchmark datasets. Furthermore, the proposed approach was compared to relevant state-of-the-art clustering algorithms, and the obtained results demonstrate the impact of using minimal previous knowledge about the data in improving the overall clustering performance.

Dealing with controversial information is an important issue in several application contexts. Formal argumentation enables reasoning on arguments for and against a claim to decide on an outcome. Dung's abstract Argumentation Framework (AF) has emerged as a central formalism in argument-based reasoning. Key aspects of the success and popularity of Dung's framework include its simplicity and expressiveness. Integrity constraints help to express domain knowledge in a compact and natural way, thus keeping easy the modeling task even for problems that otherwise would be hard to encode within an AF. In this paper, we first explore two intuitive semantics based on Kleene and Lukasiewicz logics, respectively, for AF augmented with (strong) constraints—the resulting argumentation framework is called Constrained AF (CAF). Then, we propose a new argumentation framework called Weak constrained AF (WAF) that enhances CAF with weak constraints. Intuitively, these constraints can be used to find "optimal" solutions to problems defined through CAF. We provide a detailed complexity analysis of CAF and WAF, showing that strong constraints do not increase the expressive power of AF in most cases, while weak constraints systematically increase the expressive power of CAF (and AF) under several well-known argumentation semantics. [ABSTRACT FROM AUTHOR]

The alignment stability and controllability deteriorate considerably when the air spring vibration isolation system for the high power density main engine (HPDME-ASVIS) is in a special running state of high power and high output torque. The coupling characteristics among the alignment components are obtained by analyzing the mechanical characteristics of HPDME-ASVIS. A control response model is established, which can predict the alignment state and the vertical displacement of air springs after k times of inflation/deflation. By solving the linear programming problem, the alignment controllability judgment models are constructed for two conditions, which are under hard constraints and soft constraints, respectively. Furthermore, alignment reconfigurability is described and an autonomous control method is established. The experimental results confirm that high output torque will cause large and serious coupling of horizontal offset, self-rotation angle, and vertical deformation of air springs. Meanwhile, hey cannot reach the given control precision range. The traditional control method under hard constraints will result in a state of oscillation and may bring many reliability problems to HPDME-ASVIS. The alignment reconfigurability analysis can judge the alignment control influence degree based on different torque accurately. The autonomous control can use the control parameters autonomous adjustment and the spatial configuration to realize the alignment control reconfigurability for two different alignment control fault states. The stability of the alignment control system in HPDME-ASVIS can be improved observably, which is of great significance to the engineering application of the high power density main engine (HPDME) in the field of marine propulsion technology. [ABSTRACT FROM AUTHOR]

Selecting a subset of candidates with various attributes under fairness constraints has been attracting considerable attention from the AI community, with applications ranging from school admissions to committee selections. The fairness constraints are usually captured by absolute upper bounds and/or lower bounds on the number of selected candidates in specific attributes. In many scenarios, however, the total number of selected candidates is not predetermined. It is, therefore, more natural to express these fairness constraints in terms of proportions of the final selection size. In this paper, we study the proportional candidate selection problem, where the goal is to select a subset of candidates with maximum cardinality while meeting certain proportional fairness constraints. We first analyze the computational complexity of the problem and show strong inapproximability results. Next, we investigate the algorithmic aspects of the problem in two directions. First, by treating the proportional fairness constraints as soft constraints, we devise two polynomial-time algorithms that could return (near) optimal solutions with bounded violations on each fairness constraint. Second, we design an exact algorithm with a fast running time in practice. Simulations based on both synthetic and publicly available data confirm the effectiveness and efficiency of our proposed algorithms. [ABSTRACT FROM AUTHOR]

The alignment stability and controllability deteriorate considerably when the air spring vibration isolation system for the high power density main engine (HPDME-ASVIS) is in a special running state of high power and high output torque. The coupling characteristics among the alignment components are obtained by analyzing the mechanical characteristics of HPDME-ASVIS. A control response model is established, which can predict the alignment state and the vertical displacement of air springs after k times of inflation/deflation. By solving the linear programming problem, the alignment controllability judgment models are constructed for two conditions, which are under hard constraints and soft constraints, respectively. Furthermore, alignment reconfigurability is described and an autonomous control method is established. The experimental results confirm that high output torque will cause large and serious coupling of horizontal offset, self-rotation angle, and vertical deformation of air springs. Meanwhile, hey cannot reach the given control precision range. The traditional control method under hard constraints will result in a state of oscillation and may bring many reliability problems to HPDME-ASVIS. The alignment reconfigurability analysis can judge the alignment control influence degree based on different torque accurately. The autonomous control can use the control parameters autonomous adjustment and the spatial configuration to realize the alignment control reconfigurability for two different alignment control fault states. The stability of the alignment control system in HPDME-ASVIS can be improved observably, which is of great significance to the engineering application of the high power density main engine (HPDME) in the field of marine propulsion technology.

In this paper, an efficient and probabilistic complete planning algorithm called Composite-space RRT is presented to address motion planning with soft constraints for spherical wrist manipulators. Firstly, we propose a novel configuration space termed Composite Configuration Space ("Composite Space" for short), which is composed of the joint space and the task space. Then, collision-free paths are generated in the composite space by the Rapidly-exploring Random Trees (RRT) algorithm. Finally, the planned paths in the composite space are mapped into the corresponding joint-space paths by a local planner. As the analytical inverse kinematics (IK) of the spherical wrist is used in the local planner, the proposed Composite-space RRT algorithm is characterized by high efficiency and no numerical iteration. Moreover, this approach can effectively improve the smoothness of the end-effector orientation path. The effectiveness of the proposed algorithm is demonstrated on the Willow Garage's PR2 simulation platform with two typical orientation-constrained cases. [ABSTRACT FROM AUTHOR]

Doctor scheduling is a complex, costly and time-consuming exercise. This study develops a constraint satisfaction and penalty minimisation scheduling model for meeting ‘hard constraints’ and minimises the cost of violating ‘soft constraints’, i.e. the user inputs, the total number of doctors to be scheduled, the maximum penalty to be met, and the minimum number of doctors to be assigned per shift. The algorithm creates a schedule which checks against all the constraints. The total schedule penalty associated with the constraint violations should be less than or equal to the user input penalty. If this condition is met, the schedule gets produced as the final and near-optimal solution. The model is managed to create a near optimal schedule with the minimal rule violations. However, it is challenging to provide a schedule with no rule violations. Such a situation is shown by the amount of computational time required to create a zero-penalty schedule, hours or even days needed to create a zero-penalty schedule. The system creates a schedule for a short period (weekly schedule) to promote flexibility; however, such a system does not promote fairness. Fairness is achieved through a cyclic schedule with rotations equal to the total number of doctors being scheduled. The system is managed to create a streamlined and flexible working environment and helped to improve the quality of healthcare. An optimization protocol can be incorporated into the system to reduce the search space and get the best optimal schedule since it is possible to get many schedules under the same user-defined parameters.

Many industrial model predictive control applications, called non-square systems, have more variables to be controlled than manipulated variables available. At these cases, the control objectives are related to keep the controlled ones within a range, instead in reference value (setpoint). Assessing the model quality of these controllers is fundamental, however, most available MPC assessment methods are setpoint dependent, providing misleading results when these are unavailable. The methods proposed by Botelho et al. (2015, 2016a, 2016b) allow the model assessment of linear MPCs independently from the setpoints. Even though such methodologies have this advantage, there is not a procedure to assess this kind of controller. Therefore, this paper presents a guideline to apply Botelho et al. (2015, 2016a, 2016b) methods in non-square MPCs. The Shell Heavy Oil Process is used as a case study. The results demonstrate that the procedure is capable of estimate the effect of modeling problems and indicate the associated controlled variable, as well as whether the problem is due to a model-plant mismatch or unmeasured disturbance in non-square controllers. • A guideline for model assessment of MPCs is presented. • The focus is model assessment of non-square systems. • The methods proposed by Botelho et al. (2015, 2016a, 2016b) are used for the modeling errors quantification. • The Shell Heavy Oil Process is used as a case study. • The method was exhaustively tested considering several scenarios randomly generated. [ABSTRACT FROM AUTHOR]

This paper presents a novel pulsatile Zone Model Predictive Control (pZMPC) for glycemic control in type 1 diabetic patients, which is an extension of the one presented in literature. Its main characteristics are (i) the explicit inclusion of a time-varying insulin on board constraint to promote a non-zero insulin delivery after a standard bolus infusion and to increase the postprandial system controllability, and (ii) the softening of this constraint to ensure closed-loop stability for an enlarged domain of attraction. Additionally, configuration methods are proposed for the insulin on board constraint based on carb counting regression models and glycemia rate of change information. In-silico results in the FDA-approved UVA/Padova simulator, under over/underestimation of the meal amounts, and under insulin sensitivity variability, show a superiority of the proposed glucose control over postprandial periods. [Display omitted] • A time-varying less restrictive insulin on board constraint was formulated. • A configuration method based on a carb-counting regression model. • Adaptive setting rooted in glycemia rate of change information. • Softening of this constraint while keeping closed-loop stability guarantee. [ABSTRACT FROM AUTHOR]

This study examines how to improve the accuracy of auto parking path tracking control; therefore, a linear model predictive control with softening constraints path tracking control strategy is proposed. Firstly, a linear time-varying predictive model of vehicle is established, and the future state of the vehicle can be predicted. The designed objective function fully considers the deviation between the predictor variable and the reference variable. Also, the relaxation factors are added to the optimization process, and the control increment of each cycle is calculated by the quadratic programming. Through rolling optimization and feedback correction, all kinds of deviations in the control process can be corrected in time. Then, the Simulink/CarSim simulation is carried out jointly. Furthermore, the path tracking simulation based on proportion–integration–differentiation control and no control is also carried out to compare with the model predictive control. Finally, a real vehicle test is carried out for model predictive control algorithm, and a comparative experiment based on proportion–integration–differentiation control and no control is carried out. [ABSTRACT FROM AUTHOR]

In this study, the authors propose a stabilising data‐based model predictive controller for systems subject to constraints in which the prediction model is inferred from experimental data of the plant using a machine learning technique. The inference method is a modification of the kinky inference tailored for model predictive control. In particular, the modified method has a lower computational effort and provides smoother predictions than the original method. The controller formulation considers soft constraints in the outputs, hard constraints in the inputs and guarantees closed‐loop robust stability as well as performance by means of the use of different control and prediction horizons and a weighted terminal cost. Under the assumption that the model of the system is Hölder continuous, they prove that the closed‐loop system is input‐to‐state stable with respect to the estimation errors. The results are demonstrated in a case study of a continuously stirred‐tank reactor. [ABSTRACT FROM AUTHOR]

The search for compounds exhibiting desired physical and chemical properties is an essential, yet complex problem in the chemical, petrochemical, and pharmaceutical industries. During the formulation of this optimization-based design problem two tasks must be taken into consideration: the automated generation of feasible molecular structures and the estimation of macroscopic properties based on the resultant structures. For this structural characteristic-based property prediction task numerous methods are available. However, the inverse problem, the design of a chemical compound exhibiting a set of desired properties from a given set of fragments is not so well studied. Since in general design problems molecular structures exhibiting several and sometimes conflicting properties should be optimized, we proposed a methodology based on the modification of the multi-objective Non-dominated Sorting Genetic Algorithm-II (NSGA-II). The originally huge chemical search space is conveniently described by the Joback estimation method. The efficiency of the algorithm was enhanced by soft and hard structural constraints, which expedite the search for feasible molecules. These constraints are related to the number of available groups (fragments), the octet rule and the validity of the branches in the molecule. These constraints are also used to introduce a special genetic operator that improves the individuals of the populations to ensure the estimation of the properties is based on only reliable structures. The applicability of the proposed method is tested on several benchmark problems.

In the classical team orienteering problem (TOP), a fixed fleet of vehicles is employed, each of them with a limited driving range. The manager has to decide about the subset of customers to visit, as well as the visiting order (routes). Each customer offers a different reward, which is gathered the first time that it is visited. The goal is then to maximize the total reward collected without exceeding the driving range constraint. This paper analyzes a more realistic version of the TOP in which the driving range limitation is considered as a soft constraint: every time that this range is exceeded, a penalty cost is triggered. This cost is modeled as a piece-wise function, which depends on factors such as the distance of the vehicle to the destination depot. As a result, the traditional reward-maximization objective becomes a non-smooth function. In addition, a second objective, regarding the design of balanced routing plans, is considered as well. A mathematical model for this non-smooth and bi-objective TOP is provided, and a biased-randomized algorithm is proposed as a solving approach.

Supplementary information has been proven to be particularly useful in many machine learning tasks. In ensemble learning for a set of trained base classifiers, there also exists abundant implicit supplementary information about the performance orderings for the trained base classifiers in previous literature. However, few classifier ensemble studies consider exploring and utilizing supplementary information. The current study proposes a new learning method for stack classifier ensembles by considering the implicit supplementary ordering information regarding a set of trained classifiers. First, a new metric learning algorithm for measuring the similarities between two arbitrary learning tasks is introduced. Second, supplementary ordering information for the trained classifiers of a given learning task is inferred based on the learned similarities and related performance results reported in the previous literature. Third, a set of ordered soft constraints is generated based on the supplementary ordering information, and achieving the optimal combination weights of the trained classifiers is formalized into a goal programming problem. The optimal combination weights are then obtained. Finally, the experimental results verify the effectiveness of the proposed new classifier ensemble method. [ABSTRACT FROM AUTHOR]

Relation extraction between medical concepts from electronic medical records has pervasive applications as well as significance. However, previous researches utilizing machine learning algorithms judge the semantic types of medical concept pair mentions independently. In fact, different concept pair mentions in the same context are of dependencies which can provide beneficial evidences for identifying their relation types. To the best of our knowledge, only one study has considered such dependencies in discharge summaries. However, its hard constraints are not applied effectively to the History of Present Illness (HPI) in electronic Medical Records. According to the writing characteristics of HPI records, we generalize two regularities of dependencies among concept pairs mentioned in an HPI record to enhance the performance of relation extraction. We incorporate the two soft constraints corresponding to the regularities and the posterior probabilities returned by a local classifier into a joint inference process which applies Integer Quadratic Programming method to carry out collective classification for all concept pair mentions in an HPI record. We implement four local classification models including support vector machine, logistics regression, random forest and piecewise convolutional neural networks to examine the performance of our approach. A series of experimental results demonstrate that our collective classification method has made a principal improvement and outperforms the other state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The Kaczmarz algorithm is an iterative orthogonal projection method for solving linear systems of equations. As compared to direct methods such as Gaussian elimination or sparse QR-factorization, this algorithm is efficient for problems with sparse matrices, as they appear in constraint-based User Interface (UI) layout specifications. We present a variant of the Kaczmarz method for solving non-square systems that can be applied to Graphical User Interface (GUI) layout problems. In its original form the Kaczmarz algorithm cannot handle soft constraints. Therefore, we propose two algorithms for handling specifications containing soft constraints using prioritized irreducible infeasible subsystem (IIS) detection and prioritized grouping constraints. If we use Kaczmarz during resizing of a window in a GUI then the system can also be under-determined. In this case, space is not distributed in an aesthetically pleasing way. To distribute the space according to the preferred size of the layout, we introduce the least squares Kaczmarz method to get the desired results. The performance and convergence of the proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods outperform Matlab’s LINPROG, a well-known efficient linear programming solver. [ABSTRACT FROM AUTHOR]

Over-constrained problems are ubiquitous in real-world decision and optimization problems. Plenty of modeling formalisms for various problem domains involving soft constraints have been proposed, such as weighted, fuzzy, or probabilistic constraints. All of them were shown to be instances of algebraic structures. In terms of modeling languages, however, the field of soft constraints lags behind the state of the art in classical constraint optimization. We introduce MiniBrass, a versatile soft constraint modeling language building on the unifying algebraic framework of partially ordered valuation structures (PVS) that is implemented as an extension of MiniZinc and MiniSearch. We first demonstrate the adequacy of PVS to naturally augment partial orders with a combination operation as used in soft constraints. Moreover, we provide the most general construction of a c-semiring from an arbitrary PVS. Both arguments draw upon elements from category theory. MiniBrass turns these theoretical considerations into practice: It offers a generic extensible PVS type system, reusable implementations of specific soft constraint formalisms as PVS types, operators for complex PVS products, and morphisms to transform PVS. MiniBrass models are compiled into MiniZinc to benefit from the wide range of solvers supporting FlatZinc. We evaluated MiniBrass on 28 “softened” MiniZinc benchmark problems with six different solvers. The results demonstrate the feasibility of our approach. [ABSTRACT FROM AUTHOR]

This paper presents a model predictive approach to directly control untripped vehicle roll-over. First, a novel real-time estimation scheme is designed to provide the vehicle roll angle using an observer on a combined model of vehicle kinematics and roll dynamics. This angle is used in an integrated directional and roll dynamics model for the prediction of vehicle states and roll-over index. The roll-over prevention objective is specified as a soft constraint to ensure persistent feasibility. If the controller foresees impending vehicle roll-over, it intervenes and reduces the roll-over index by torque vectoring. Software simulations are used to assess the effectiveness of the proposed roll-over control method in the industry standard fishhook maneuvers. In addition, the accuracy and performance of the suggested estimation and control algorithms are verified in double-lane change and flick maneuvers on dry asphalt with an instrumented test vehicle. The results show accurate estimation of the vehicle roll angle and excellent control on roll-over index with the proposed predictive roll-over controller. [ABSTRACT FROM AUTHOR]

Cluster analysis discovers natural structures from different perspectives of data objects and has become an effective method in data mining. The emergence of semi-supervised clustering techniques has improved the performance of unsupervised clustering algorithms. Clustering with guidance information is a clustering method variant that uses pairwise constraints based on background knowledge. This method increases the interpretability of the results through a knowledge-guided perspective but simultaneously suffers from the problem of constraint conflict. This paper designs knowledge augmentation-based soft constraints as a new pairwise constraint representation and proposes a Soft Constraints Kmeans (SCop-Kmeans) method to resolve constraint conflicts. By describing constraint knowledge from multiple perspectives, the association strength of pairwise constraints is calculated to obtain the assignment basis of objects. SCop-Kmeans can solve the sample allocation conflict problem caused by the contradiction between different constraints and improve the clustering stability. Finally, experiments are performed using UCI public standard datasets. The proposed method further improves the accuracy of clustering and performs well in experiments with different numbers of constraints, which shows that the proposed method has advantages in using constraint information to guide clustering. • A knowledge augmentation-based semi-supervised clustering method is proposed to deal with the constraint conflict scenario in pairwise constraint semi-supervised clustering. • The method expresses the link strength of constraints by expanding constraint knowledge from multiple perspectives. • The method reduces the computational complexity by preserving the soft constraint matrix results. • The operation process of the method is incremental and has online availability. • The effectiveness of the method is demonstrated on UCI public datasets in 12 different domains. [ABSTRACT FROM AUTHOR]

The paper proposes a transparent approach for mapping the status of environmental phenomena from multisource information based on both soft computing and machine learning. It is transparent, intended as human understandable as far as the employed criteria, and both knowledge and data-driven. It exploits remote sensing experts’ interpretations to define the contributing factors from which partial evidence of the environmental status are computed by processing multispectral images. Furthermore, it computes an environmental status indicator (ESI) map by aggregating the partial evidence degrees through a learning mechanism, exploiting volunteered geographic information (VGI). The approach is capable of capturing the specificities of local context, as well as to cope with the subjectivity of experts’ interpretations. The proposal is applied to map the status of standing water areas (i.e., water bodies and rivers and human-driven or natural hazard flooding) using multispectral optical images by ESA Sentinel-2 sources. VGI comprises georeferenced observations created both in situ by agronomists using a mobile application and by photointerpreters interacting with a geographic information system (GIS) using several information layers. Results of the validation experiments were performed in three areas of Northern Italy characterized by distinct ecosystems. The proposal showed better performances than traditional methods based on single spectral indexes.

Soft constraints are quite common in real-life applications. For example, in freight transportation, the fleet size can be enlarged by outsourcing part of the distribution service and some deliveries to customers can be postponed as well; in inventory management, it is possible to consider stock-outs generated by unexpected demands; and in manufacturing processes and project management, it is frequent that some deadlines cannot be met due to delays in critical steps of the supply chain. However, capacity-, size-, and time-related limitations are included in many optimization problems as hard constraints, while it would be usually more realistic to consider them as soft ones, i.e., they can be violated to some extent by incurring a penalty cost. Most of the times, this penalty cost will be nonlinear and even noncontinuous, which might transform the objective function into a non-smooth one. Despite its many practical applications, non-smooth optimization problems are quite challenging, especially when the underlying optimization problem is NP-hard in nature. In this paper, we propose the use of biased-randomized algorithms as an effective methodology to cope with NP-hard and non-smooth optimization problems in many practical applications. Biased-randomized algorithms extend constructive heuristics by introducing a nonuniform randomization pattern into them. Hence, they can be used to explore promising areas of the solution space without the limitations of gradient-based approaches, which assume the existence of smooth objective functions. Moreover, biased-randomized algorithms can be easily parallelized, thus employing short computing times while exploring a large number of promising regions. This paper discusses these concepts in detail, reviews existing work in different application areas, and highlights current trends and open research lines.

Visual cues relating to an interrupted task can help people recover from workplace interruptions. However, it is unclear whether visual cues relating to their next steps in a primary task may help people manage interruptions. In a previous intensive care unit simulation study, Grundgeiger et al. (2013) found that nurses performing equipment checks were more likely to defer an interruption from a colleague if they could see the next steps of their task on the equipment screen. We abstracted some elements of the simulation study into a controlled laboratory study to test whether visual cues support interruption management. Participants' primary task was to verify a set of linked arithmetic equations presented on a computer page. From time to time, an animated virtual character interrupted the participant to mimic a social interruption, and the participant chose whether or not to defer a response to the interruptions until they finished their page of equations. In four experiments, the independent variable was visual cue (cue versus no cue) and the primary outcome was the proportion of interruptions from the character that the participant deferred so that she or he could complete the page of equations. Ex­per­i­ment 1 (in English) sug­gested that the vi­sual cue made par­tic­i­pants more likely to de­fer the in­ter­rup­tion. How­ever, a po­ten­tial con­found noted in Ex­per­i­ment 1 was elim­i­nated in Ex­per­i­ment 2 (also in English) and the ef­fect of the vi­sual cue dis­ap­peared. Experiment 3 (in German) tested a different way to remove the confound and replicated the results of Experiment 2. Finally Experiment 4 (in German) restored the confound and replicated the results of Experiment 1. Par­tic­i­pants’ de­ci­sions to de­fer in­ter­rup­tions can de­pend on ap­par­ently mi­nor prop­er­ties of their pri­mary task. [ABSTRACT FROM AUTHOR]

Linear relaxation is a common method for solving linear problems, as they occur in science and engineering. In contrast to direct methods such as Gauss-elimination or QR-factorization, linear relaxation is particularly efficient for problems with sparse matrices, as they appear in constraint-based user interface (UI) layout specifications. However, the linear relaxation method as described in the literature has its limitations: it works only with square matrices and does not support soft constraints, which makes it inapplicable to the UI layout problem. To overcome these limitations we propose two algorithms for selecting the pivot elements used during linear relaxation: random pivot assignment, and a more complex deterministic pivot assignment. Furthermore, we propose three algorithms for solving specifications containing soft constraints: prioritized IIS detection, prioritized deletion filtering and prioritized grouping constraints. With these algorithms, it is possible to prioritize constraints: if there are conflicting constraints in a specification, as it is commonly the case for UI layout, only the constraints with lower priority are violated to resolve the conflicts. The performance and convergence of the proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that our best linear relaxation algorithm performs significantly better than Matlab’s LINPROG, a well-known efficient linear programming solver. [ABSTRACT FROM AUTHOR]

Combinatorial optimisation problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with an objective function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism as it is a simple yet powerful setting having these features. We study the learnability of MAX-SAT models. Our theoretical results show that high-quality MAX-SAT models can be learned from contextual examples in the realisable and agnostic settings, as long as the data satisfies an intuitive "representativeness" condition. We also contribute two implementations based on our theoretical results: one leverages ideas from syntax-guided synthesis while the other makes use of stochastic local search techniques. The two implementations are evaluated by recovering synthetic and benchmark models from contextual examples. The experimental results support our theoretical analysis, showing that MAX-SAT models can be learned from contextual examples. Among the two implementations, the stochastic local search learner scales much better than the syntax-guided implementation while providing comparable or better models. [ABSTRACT FROM AUTHOR]

Constraints that express relationships among objects are used to model and solve various problems arising from fields such as artificial intelligence, software, and computer graphics. Soft constraints are often important for applications that involve complex relationships among objects. This paper proposes a new method for solving soft constraints. The method treats soft nonlinear con- straints with hierarchical preferences, and computes solutions that satisfy as many constraints with strong preferences as possible. It adopts the method of Lagrange multipliers to enable the accurate computation of local solutions. The paper also presents the result of a preliminary experiment using a simple geometric example. [ABSTRACT FROM AUTHOR]

Hildreth’s algorithm is a row action method for solving large systems of inequalities. This algorithm is efficient for problems with sparse matrices, as opposed to direct methods such as Gaussian elimination or QR-factorization. We apply Hildreth’s algorithm, as well as a randomized version, along with prioritized selection of the inequalities, to efficiently detect the highest priority feasible subsystem of equations. We prove convergence results and feasibility criteria for both cyclic and randomized Hildreth’s algorithm, as well as a mixed algorithm which uses Hildreth’s algorithm for inequalities and Kaczmarz algorithm for equalities. These prioritized, sparse systems of inequalities commonly appear in constraint-based user interface (UI) layout specifications. The performance and convergence of these proposed algorithms are evaluated empirically using randomly generated UI layout specifications of various sizes. The results show that these methods offer improvements in performance over standard methods like Matlab’s LINPROG, a well-known efficient linear programming solver, and the recent developed Kaczmarz algorithm with prioritized IIS detection. [ABSTRACT FROM AUTHOR]

Constraint-based pattern discovery is at the core of numerous data mining tasks. Patterns are extracted with respect to a given set of constraints (frequency, closedness, size, etc). In practice, many constraints require threshold values whose choice is often arbitrary. This difficulty is even harder when several thresholds are required and have to be combined. Moreover, patterns barely missing a threshold will not be extracted even if they may be relevant. The paper advocates the introduction of softness into the pattern discovery process. By using Constraint Programming, we propose efficient methods to relax threshold constraints as well as constraints involved in patterns such as the top- k patterns and the skypatterns. We show the relevance and the efficiency of our approach through a case study in chemoinformatics for discovering toxicophores. [ABSTRACT FROM AUTHOR]

The current work investigates the capability of a tailored multivariate curve resolution–alternating least squares (MCR-ALS) algorithm to analyse glucose, phosphate, ammonium and acetate dynamics simultaneously in an E. coli BL21 fed-batch fermentation. The high-cell-density (HCDC) process is monitored by ex situ online attenuated total reflection (ATR) Fourier transform infrared (FTIR) spectroscopy and several in situ online process sensors. This approach efficiently utilises automatically generated process data to reduce the time and cost consuming reference measurement effort for multivariate calibration. To determine metabolite concentrations with accuracies between ±0.19 and ±0.96·gL−l, the presented utilisation needs primarily—besides online sensor measurements—single FTIR measurements for each of the components of interest. The ambiguities in alternating least squares solutions for concentration estimation are reduced by the insertion of analytical process knowledge primarily in the form of elementary carbon mass balances. Thus, in this way, the established idea of mass balance constraints in MCR combines with the consistency check of measured data by carbon balances, as commonly applied in bioprocess engineering. The constraints are calculated based on online process data and theoretical assumptions. This increased calculation effort is able to replace, to a large extent, the need for manually conducted quantitative chemical analysis, leads to good estimations of concentration profiles and a better process understanding.

Soft constraints and penalty functions are commonly used in MPC to ensure that the optimization problem has a feasible solution, and thereby avoid MPC controller failure. On the other hand, soft constraints may allow for unnecessary violations of the original constraints, i.e. , the constraints may be violated even if a valid solution that does not violate any constraints exists. The paper develops procedures for the minimizing (according to some norm) of the Lagrange multipliers associated with a given mp-QP problem, assumed to originate from an MPC problem formulation. To this end the LICQ condition is exploited in order to efficiently formulate the optimization problem, and thereby improve upon existing mixed integer formulations and enhance the tractability of the problem. The results are used to design penalty functions such that corresponding soft constraints are made exact, that is, the original (hard) constraints are violated only if there exists no solution where all constraints are satisfied. [ABSTRACT FROM AUTHOR]

Abstract: Proteins are chains of simple molecules called amino acids. The three-dimensional shape of a protein and its amino acid composition define its biological function. Over millions of years, living organisms have evolved a large catalog of proteins. By exploring the space of possible amino acid sequences, protein engineering aims at similarly designing tailored proteins with specific desirable properties. In Computational Protein Design (CPD), the challenge of identifying a protein that performs a given task is defined as the combinatorial optimization of a complex energy function over amino acid sequences. In this paper, we introduce the CPD problem and some of the main approaches that have been used by structural biologists to solve it, with an emphasis on the exact method embodied in the dead-end algorithm . The CPD problem is a specific form of binary Cost Function Network (CFN, aka Weighted CSP). We show how DEE algorithms can be incorporated and suitably modified to be maintained during search, at reasonable computational cost. We then evaluate the efficiency of CFN algorithms as implemented in our solver toulbar2, on a set of real CPD instances built in collaboration with structural biologists. The CPD problem can be easily reduced to 0/1 Linear Programming, 0/1 Quadratic Programming, 0/1 Quadratic Optimization, Weighted Partial MaxSAT and Graphical Model optimization problems. We compare toulbar2 with these different approaches using a variety of solvers. We observe tremendous differences in the difficulty that each approach has on these instances. Overall, the CFN approach shows the best efficiency on these problems, improving by several orders of magnitude against the exact approach. The introduction of dead-end elimination before or during search allows to further improve these results. [Copyright &y& Elsevier]

Highlights: [•] We propose a constrained two dimensional recursive least square system identification method. [•] Incorporate a penalty term into cost function to smooth identified parameters. [•] Study the weights selection on the penalty term. [ABSTRACT FROM AUTHOR]