Graph-Based Multi-Surface Segmentation of OCT Data Using Trained Hard and Soft Constraints

Optical coherence tomography (OCT) is a well-established image modality in ophthalmology and used daily in the clinic. Automatic evaluation of such datasets requires an accurate segmentation of the retinal cell layers. However, due to the naturally low signal to noise ratio and the resulting bad image quality, this task remains challenging. We propose an automatic graph-based multi-surface segmentation algorithm that internally uses soft constraints to add prior information from a learned model. This improves the accuracy of the segmentation and increase the robustness to noise. Furthermore, we show that the graph size can be greatly reduced by applying a smart segmentation scheme. This allows the segmentation to be computed in seconds instead of minutes, without deteriorating the segmentation accuracy, making it ideal for a clinical setup. An extensive evaluation on 20 OCT datasets of healthy eyes was performed and showed a mean unsigned segmentation error of 3.05 ±0.54 μm over all datasets when compared to the average observer, which is lower than the inter-observer variability. Similar performance was measured for the task of drusen segmentation, demonstrating the usefulness of using soft constraints as a tool to deal with pathologies.

Hyperspectral imagery framework for unmixing and dimensionality estimation

In hyperspectral imagery a pixel typically consists mixture of spectral signatures of reference substances, also called endmembers. Linear spectral mixture analysis, or linear unmixing, aims at estimating the number of endmembers, their spectral signatures, and their abundance fractions. This paper proposes a framework for hyperpsectral unmixing. A blind method (SISAL) is used for the estimation of the unknown endmember signature and their abundance fractions. This method solve a non-convex problem by a sequence of augmented Lagrangian optimizations, where the positivity constraints, forcing the spectral vectors to belong to the convex hull of the endmember signatures, are replaced by soft constraints. The proposed framework simultaneously estimates the number of endmembers present in the hyperspectral image by an algorithm based on the minimum description length (MDL) principle. Experimental results on both synthetic and real hyperspectral data demonstrate the effectiveness of the proposed algorithm.

User-centric product derivation in software product lines

Software Product Line (SPL) engineering aims at achieving efficient development of software products in a specific domain. New products are obtained via a process which entails creating a new configuration specifying the desired product’s features. This configuration must necessarily conform to a variability model, that describes the scope of the SPL, or else it is not viable. To ensure this, configuration tools are used that do not allow invalid configurations to be expressed. A different concern, however, is making sure that a product addresses the stakeholders’ needs as best as possible. The stakeholders may not be experts on the domain, so they may have unrealistic expectations. Also, the scope of the SPL is determined not only by the domain but also by limitations of the development platforms. It is therefore possible that the desired set of features goes beyond what is possible to currently create with the SPL. This means that configuration tools should provide support not only for creating valid products, but also for improving satisfaction of user concerns. We address this goal by providing a user-centric configuration process that offers suggestions during the configuration process, based on the use of soft constraints, and identifying and explaining potential conflicts that may arise. Suggestions help mitigating stakeholder uncertainty and poor domain knowledge, by helping them address well known and desirable domain-related concerns. On the other hand, automated conflict identification and explanation helps the stakeholders to understand the trade-offs required for realizing their vision, allowing informed resolution of conflicts. Additionally, we propose a prototype-based approach to configuration, that addresses the order-dependency issues by allowing the complete (or partial) specification of the features in a single step. A subsequent resolution process will then identify possible repairs, or trade-offs, that may be required for viabilization.

Una metodología eficiente para manejo de restricciones en algoritmos evolutivos multi-objetivo

This paper presents a new approach for solving constraint optimization problems (COP) based on the philosophy of lexicographical goal programming. A two-phase methodology for solving COP using a multi-objective strategy is used. In the first phase, the objective function is completely disregarded and the entire search effort is directed towards finding a single feasible solution. In the second phase, the problem is treated as a bi-objective optimization problem, turning the constraint optimization into a two-objective optimization. The two resulting objectives are the original objective function and the constraint violation degree. In the first phase a methodology based on progressive hardening of soft constraints is proposed in order to find feasible solutions. The performance of the proposed methodology was tested on 11 well-known benchmark functions.

A heuristic algorithm based on multi-assignment procedures for nurse scheduling

This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses' preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust. © 2013 Springer Science+Business Media New York.

Reasoning with incomplete and imprecise preferences

Preferences are present in many real life situations but it is often difficult to quantify them giving a precise value. Sometimes preference values may be missing because of privacy reasons or because they are expensive to obtain or to produce. In some other situations the user of an automated system may have a vague idea of whats he wants. In this thesis we considered the general formalism of soft constraints, where preferences play a crucial role and we extended such a framework to handle both incomplete and imprecise preferences. In particular we provided new theoretical frameworks to handle such kinds of preferences. By admitting missing or imprecise preferences, solving a soft constraint problem becomes a different task. In fact, the new goal is to find solutions which are the best ones independently of the precise value the each preference may have. With this in mind we defined two notions of optimality: the possibly optimal solutions and the necessary optimal solutions, which are optimal no matter we assign a precise value to a missing or imprecise preference. We provided several algorithms, bases on both systematic and local search approaches, to find such kind of solutions. Moreover, we also studied the impact of our techniques also in a specific class of problems (the stable marriage problems) where imprecision and incompleteness have a specific meaning and up to now have been tackled with different techniques. In the context of the classical stable marriage problem we developed a fair method to randomly generate stable marriages of a given problem instance. Furthermore, we adapted our techniques to solve stable marriage problems with ties and incomplete lists, which are known to be NP-hard, obtaining good results both in terms of size of the returned marriage and in terms of steps need to find a solution.

Hyperspectral unmixing with simultaneous dimensionality estimation

This paper is an elaboration of the simplex identification via split augmented Lagrangian (SISAL) algorithm (Bioucas-Dias, 2009) to blindly unmix hyperspectral data. SISAL is a linear hyperspectral unmixing method of the minimum volume class. This method solve a non-convex problem by a sequence of augmented Lagrangian optimizations, where the positivity constraints, forcing the spectral vectors to belong to the convex hull of the endmember signatures, are replaced by soft constraints. With respect to SISAL, we introduce a dimensionality estimation method based on the minimum description length (MDL) principle. The effectiveness of the proposed algorithm is illustrated with simulated and real data.

A Decomposition, Construction and Post-Processing Approach for Nurse Rostering

This paper presents our work on decomposing a specific nurse rostering problem by cyclically assigning blocks of shifts, which are designed considering both hard and soft constraints, to groups of nurses. The rest of the shifts are then assigned to the nurses to construct a schedule based on the one cyclically generated by blocks. The schedules obtained by decomposition and construction can be further improved by a variable neighborhood search. Significant results are obtained and compared with a genetic algorithm and a variable neighborhood search approach on a problem that was presented to us by our collaborator, ORTEC bv, The Netherlands. We believe that the approach has the potential to be further extended to solve a wider range of nurse rostering problems.

Scheduling of track inspection and maintenance activities in railroad networks

The U.S. railroad companies spend billions of dollars every year on railroad track maintenance in order to ensure safety and operational efficiency of their railroad networks. Besides maintenance costs, other costs such as train accident costs, train and shipment delay costs and rolling stock maintenance costs are also closely related to track maintenance activities. Optimizing the track maintenance process on the extensive railroad networks is a very complex problem with major cost implications. Currently, the decision making process for track maintenance planning is largely manual and primarily relies on the knowledge and judgment of experts. There is considerable potential to improve the process by using operations research techniques to develop solutions to the optimization problems on track maintenance. In this dissertation study, we propose a range of mathematical models and solution algorithms for three network-level scheduling problems on track maintenance: track inspection scheduling problem (TISP), production team scheduling problem (PTSP) and job-to-project clustering problem (JTPCP). TISP involves a set of inspection teams which travel over the railroad network to identify track defects. It is a large-scale routing and scheduling problem where thousands of tasks are to be scheduled subject to many difficult side constraints such as periodicity constraints and discrete working time constraints. A vehicle routing problem formulation was proposed for TISP, and a customized heuristic algorithm was developed to solve the model. The algorithm iteratively applies a constructive heuristic and a local search algorithm in an incremental scheduling horizon framework. The proposed model and algorithm have been adopted by a Class I railroad in its decision making process. Real-world case studies show the proposed approach outperforms the manual approach in short-term scheduling and can be used to conduct long-term what-if analyses to yield managerial insights. PTSP schedules capital track maintenance projects, which are the largest track maintenance activities and account for the majority of railroad capital spending. A time-space network model was proposed to formulate PTSP. More than ten types of side constraints were considered in the model, including very complex constraints such as mutual exclusion constraints and consecution constraints. A multiple neighborhood search algorithm, including a decomposition and restriction search and a block-interchange search, was developed to solve the model. Various performance enhancement techniques, such as data reduction, augmented cost function and subproblem prioritization, were developed to improve the algorithm. The proposed approach has been adopted by a Class I railroad for two years. Our numerical results show the model solutions are able to satisfy all hard constraints and most soft constraints. Compared with the existing manual procedure, the proposed approach is able to bring significant cost savings and operational efficiency improvement. JTPCP is an intermediate problem between TISP and PTSP. It focuses on clustering thousands of capital track maintenance jobs (based on the defects identified in track inspection) into projects so that the projects can be scheduled in PTSP. A vehicle routing problem based model and a multiple-step heuristic algorithm were developed to solve this problem. Various side constraints such as mutual exclusion constraints and rounding constraints were considered. The proposed approach has been applied in practice and has shown good performance in both solution quality and efficiency.

Constraint-Informed Information Systems in Space Management Utilization

Declarative techniques such as Constraint Programming can be very effective in modeling and assisting management decisions. We present a method for managing university classrooms which extends the previous design of a Constraint-Informed Information System to generate the timetables while dealing with spatial resource optimization issues. We seek to maximize space utilization along two dimensions: classroom use and occupancy rates. While we want to maximize the room use rate, we still need to satisfy the soft constraints which model students’ and lecturers’ preferences. We present a constraint logic programming-based local search method which relies on an evaluation function that combines room utilization and timetable soft preferences. Based on this, we developed a tool which we applied to the improvement of classroom allocation in a University. Comparing the results to the current timetables obtained without optimizing space utilization, the initial versions of our tool manages to reach a 30% improvement in space utilization, while preserving the quality of the timetable, both for students and lecturers.

Fiscal sustainability across government tiers: an assessment of soft budget constraints

This paper analyses how fiscal adjustment comes about when both central and sub-national governments are involved in consolidation. We test sustainability of public debt with a fiscal rule for both the federal and regional government. Results for the German Länder show that lower tier governments bear a relatively smaller part of the burden of debt consolidation, if they consolidate at all. Most of the fiscal adjustment occurs via central government debt. In contrast, both the US federal and state levels contribute to consolidation of public finances.

«School choice with controlled choice constraints: hard bounds versus soft bounds»

Controlled choice over public schools attempts giving options to parents while maintaining diversity, often enforced by setting feasibility constraints with hard upper and lower bounds for each student type. We demonstrate that there might not exist assignments that satisfy standard fairness and non-wastefulness properties; whereas constrained non-wasteful assignments which are fair for same type students always exist. We introduce a "controlled" version of the deferred acceptance algorithm with an improvement stage (CDAAI) that finds a Pareto optimal assignment among such assignments. To achieve fair (across all types) and non-wasteful assignments, we propose the control constraints to be interpreted as soft bounds-flexible limits that regulate school priorities. In this setting, a modified version of the deferred acceptance algorithm (DAASB) finds an assignment that is Pareto optimal among fair assignments while eliciting true preferences. CDAAI and DAASB provide two alternative practical solutions depending on the interpretation of the control constraints. JEL C78, D61, D78, I20.

Soft budget constraints in a dynamic general equilibrium model

This paper considers an overlapping generations model in which capital investment is financed in a credit market with adverse selection. Lenders’ inability to commit ex-ante not to bailout ex-post, together with a wealthy position of entrepreneurs gives rise to the soft budget constraint syndrome, i.e. the absence of liquidation of poor performing firms on a regular basis. This problem arises endogenously as a result of the interaction between the economic behavior of agents, without relying on political economy explanations. We found the problem more binding along the business cycle, providing an explanation to creditors leniency during booms in some LatinAmerican countries in the late seventies and early nineties.

Soft Budget Constraints and Regional Industrial Policy: Reinterpreting the Rise and fall of De Lorean

The rise and fall of De Lorean Motor Cars Limited (DMCL) has been traditionally interpreted as either the result either of John De Lorean’s psychological flaws or as confirming the supposed limitations of activist industrial policy. However, when the episode is examined in greater historical detail, neither of these interpretations are compelling. The reinterpretation outlined here draws on institutional analysis as well as a range of archival sources, much of it previously unreleased. The inefficiencies within the original contractual agreement are highlighted. The lack of credibility associated with this agreement was in turn traceable to the institutional environment (with its associated risk-reward implications) under which industrial policy operated. This environment had a political element - it had been distorted by the Troubles and the resulting fears policymakers had of a cumulative causation relationship between violence and unemployment. Officials in Belfast, against Treasury opposition, advocated state-led entrepreneurship as a policy response.