Approximated consistency for the automatic recording constraint

We introduce the automatic recording constraint (ARC) that can be used to model and solve scheduling problems where tasks may not overlap in time and the tasks linearly exhaust some resource. Since achieving generalized arc-consistency for the ARC is NP-hard, we develop a filtering algorithm that achieves approximated consistency only. Numerical results show the benefits of the new constraint on three out of four different types of benchmark sets for the automatic recording problem. On these instances, run-times can be achieved that are orders of magnitude better than those of the best previous constraint programming approach.     

Scheduling on-demand broadcast with timing constraints

In a distributed system, broadcasting is an efficient way to dispense data in certain highly dynamic environments. While there are several well-known on-line broadcast scheduling strategies that minimize wait time, there has been little research that considers on-demand broadcasting with timing constraints. One application which could benefit from a strategy for on-demand broadcast with timing constraints is a real-time database system. Scheduling strategies are needed in real-time databases that identify which data item to broadcast next in order to minimize missed deadlines. The scheduling decisions required in a real-time broadcast system allow the system to be modeled as a Markov Decision Process (MDP). In this paper, we analyze the MDP model and determine that finding an optimal solution is a hard problem in PSPACE. We propose a scheduling approach, called Aggregated Critical Requests (ACR), which is based on the MDP formulation and present two algorithms based on this approach. ACR is designed for timely delivery of data to clients in order to maximize the reward by minimizing the deadlines missed. Results from trace-driven experiments indicate the ACR approach provides a flexible strategy that can outperform existing strategies under a variety of factors.     

Optimal Control of Discrete Event Systems with Weakly Hard Real-Time Constraints

We consider Discrete Event Systems that can dynamically allocate resources in order to process tasks with real-time constraints. In the case of “weakly hard” constraints, a fraction of tasks is allowed to violate them, as long as m out of any k consecutive tasks meet their respective constraints. This is a generalization of a system with purely hard real-time constraints where m = k = 1. For non-preemptive and aperiodic tasks, we formulate an optimization problem where task processing times are controlled so as to minimize a cost function while guaranteeing that a “weakly hard” criterion is satisfied. We establish a number of structural properties of the solution to this problem which lead to an efficient algorithm that does not require any explicit nonlinear programming problem solver. The low complexity of this algorithm makes it suitable for on-line applications. Simulation examples illustrate the performance improvements in such optimally controlled systems compared to ad hoc schemes.

Network Topology and Locational Market Power

This paper studies the effect of network topology and production constraints on the locational market power of generators. A market power spectrum is considered where one end has infinitely large production capacity but the usual network constraints while the other end has infinitely large network capacity but the usual production constraints. First, we analyze the locational market power function mathematically. Then, we use a real world example of the Portland, Oregon electrical market and determine its position on the market power spectrum. We find the Portland market to be primarily production constrained rather than network constrained. We also identify the local and global threshold generation capacities for each generator beyond which it cannot influence the individual and total locational market power, respectively. This study facilitates the understanding of the economic and physical determinants of locational market power. It can help regulators make informed decisions when it comes to the choice of enhancing the physical infrastructure, or adding more generation capacity to the market.     

A notion of possible controllability for uncertain linear systems with structured uncertainty

This paper introduces a notion of possible controllability for a class of uncertain linear systems with structured uncertainty described by averaged integral quadratic constraints. This notion relates to the question of when a state is controllable for some possible value of the uncertainty. The notion of possible controllability is motivated by a desire to extend the theory of minimal realization for linear time invariant systems to the case of uncertain systems with structured uncertainty.     

Generalized bang-bang control for feedforward constrained regulation

In the behavioral framework for continuous-time linear scalar systems, simple sufficient conditions for the solution of the minimum-time rest-to-rest feedforward constrained control problem are provided. The investigation of the time-optimal input-output pair reveals that the input or the output saturates on the assigned constraints at all times except for a set of zero measure. The resulting optimal input is composed of sequences of bang-bang functions and linear combinations of the modes associated to the zero dynamics. This signal behavior constitutes a generalized bang-bang control that can be fruitfully exploited for feedforward constrained regulation. Using discretization, an arbitrarily good approximation of the optimal generalized bang-bang control is found by solving a sequence of linear programming problems. Numerical examples are included.     

A note on some collapse results of valued constraints

Valued constraint satisfaction problem (VCSP) is an optimisation framework originally coming from Artificial Intelligence and generalising the classical constraint satisfaction problem (CSP). The VCSP is powerful enough to describe many important classes of problems. In order to investigate the complexity and expressive power of valued constraints, a number of algebraic tools have been developed in the literature. In this note we present alternative proofs of some known results without using the algebraic approach, but by representing valued constraints explicitly by combinations of other valued constraints.     

Detection of unexpected multi-part objects from segmented contour maps

A novel method is proposed to detect multi-part objects of unknown specific shape and appearance in natural images. It consists in first extracting a strictly over-segmented map of circular arcs and straight-line segments from an edge map. Each obtained constant-curvature contour primitive has an unknown origin which may be the external boundary of an interesting object, the textured or marked region enclosed by that boundary, or the external background region. The following processing steps identify, in a systematic yet efficient way, which groups of ordered contour primitives form a complete boundary of proper multi-part shape. Multiple detections are ranked with the top boundaries best satisfying a combination of global shape grouping criteria. Experimental results confirm the unique potential of the method to identify, in images of variable complexity, actual boundaries of multi-part objects as diverse as an airplane, a stool, a bicycle, a fish, and a toy truck.     

Loss optimal monotone relabeling of noisy multi-criteria data sets

A method to relabel noisy multi-criteria data sets is presented, taking advantage of the transitivity of the non-monotonicity relation to formulate the problem as an efficiently solvable maximum independent set problem. A framework and an algorithm for general loss functions are presented, and the flexibility of the approach is indicated by some examples, showcasing the ease with which the method can handle application-specific loss functions. Both didactical examples and real-life applications are provided, using the zero-one, the L1 and the squared loss functions, as well as combinations thereof.     

SuperIso Relic: A program for calculating relic density and flavor physics observables in Supersymmetry

We describe SuperIso Relic, a public program for evaluation of relic density and flavor physics observables in the minimal supersymmetric extension of the Standard Model (MSSM). SuperIso Relic is an extension of the SuperIso program which adds to the flavor observables of SuperIso the computation of all possible annihilation and coannihilation processes of the LSP which are required for the relic density calculation. All amplitudes have been generated at the tree level with FeynArts/FormCalc, and widths of the Higgs bosons are computed with FeynHiggs at the two-loop level. SuperIso Relic also provides the possibility to modify the assumptions of the cosmological model, and to study their consequences on the relic density.

Program summary

Program title: SuperIso RelicCatalogue identifier: AEGD_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEGD_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: yesNo. of lines in distributed program, including test data, etc.: 2 274 720No. of bytes in distributed program, including test data, etc.: 6 735 649Distribution format: tar.gzProgramming language: C (C99 Standard compliant) and FortranComputer: 32- or 64-bit PC, MacOperating system: Linux, MacOSRAM: 100 MbClassification: 1.9, 11.6External routines: ISASUGRA/ISAJET and/or SOFTSUSY, FeynHiggsDoes the new version supersede the previous version?: No (AEAN_v2_0)Nature of problem: Calculation of the lightest supersymmetric particle relic density, as well as flavor physics observables, in order to derive constraints on the supersymmetric parameter space.Solution method: SuperIso Relic uses a SUSY Les Houches Accord file, which can be either generated automatically via a call to SOFTSUSY or ISAJET, or provided by the user. This file contains the masses and couplings of the supersymmetric particles. SuperIso Relic then computes the lightest supersymmetric particle relic density as well as the most constraining flavor physics observables. To do so, it calculates first the widths of the Higgs bosons with FeynHiggs, and then it evaluates the squared amplitudes of the diagrams needed for the relic density calculation. These thousands of diagrams have been previously generated with the FeynArts/FormCalc package. SuperIso Relic is able to perform the calculations in different supersymmetry breaking scenarios, such as mSUGRA, NUHM, AMSB and GMSB.Reasons for new version: This version incorporates the calculation of the relic density, which is often used to constrain Supersymmetry.Summary of revisions:

•

Addition of the relic density calculation

•

Replacement of "float" type by "double".

Unusual features: SuperIso Relic includes the possibility of altering the underlying cosmological model and testing the influence of the cosmological assumptions.Additional comments: This program is closely associated with the "SuperIso" program - CPC Program Library, Catalogue Id. AEAN.Running time:Compilation time: a couple of hours for the statically linked version, a few minutes for the dynamically linked version. Running time: about 1 second, or a few seconds if libraries need to be compiled on the fly.