Comparison of Work Scheduling Using Constraint Programming or Auctions

Business processes designers take into account the resources that the processes would need, but, due to the variable cost of certain parameters (like energy) or other circumstances, this scheduling must be done when business process enactment. In this report we formalize the energy aware resource cost, including time and usage dependent rates. We also present a constraint programming approach and an auction-based approach to solve the mentioned problem including a comparison of them and a comparison of the proposed algorithms for solving them

Assembling genes from predicted exons in linear time with dynamic programming

In a number of programs for gene structure prediction in higher eukaryotic genomic sequences, exon prediction is decoupled from gene assembly: a large pool of candidate exons is predicted and scored from features located in the query DNA sequence, and candidate genes are assembled from such a pool as sequences of nonoverlapping frame-compatible exons. Genes are scored as a function of the scores of the assembled exons, and the highest scoring candidate gene is assumed to be the most likely gene encoded by the query DNA sequence. Considering additive gene scoring functions, currently available algorithms to determine such a highest scoring candidate gene run in time proportional to the square of the number of predicted exons. Here, we present an algorithm whose running time grows only linearly with the size of the set of predicted exons. Polynomial algorithms rely on the fact that, while scanning the set of predicted exons, the highest scoring gene ending in a given exon can be obtained by appending the exon to the highest scoring among the highest scoring genes ending at each compatible preceding exon. The algorithm here relies on the simple fact that such highest scoring gene can be stored and updated. This requires scanning the set of predicted exons simultaneously by increasing acceptor and donor position. On the other hand, the algorithm described here does not assume an underlying gene structure model. Indeed, the definition of valid gene structures is externally defined in the so-called Gene Model. The Gene Model specifies simply which gene features are allowed immediately upstream which other gene features in valid gene structures. This allows for great flexibility in formulating the gene identification problem. In particular it allows for multiple-gene two-strand predictions and for considering gene features other than coding exons (such as promoter elements) in valid gene structures.

Predictability of music descriptor time series and its application to cover song detection

Intuitively, music has both predictable and unpredictable components. In this work we assess this qualitative statement in a quantitative way using common time series models fitted to state-of-the-art music descriptors. These descriptors cover different musical facets and are extracted from a large collection of real audio recordings comprising a variety of musical genres. Our findings show that music descriptor time series exhibit a certain predictability not only for short time intervals, but also for mid-term and relatively long intervals. This fact is observed independently of the descriptor, musical facet and time series model we consider. Moreover, we show that our findings are not only of theoretical relevance but can also have practical impact. To this end we demonstrate that music predictability at relatively long time intervals can be exploited in a real-world application, namely the automatic identification of cover songs (i.e. different renditions or versions of the same musical piece). Importantly, this prediction strategy yields a parameter-free approach for cover song identification that is substantially faster, allows for reduced computational storage and still maintains highly competitive accuracies when compared to state-of-the-art systems.

Chroma binary similarity and local alignment applied to cover song identification

We present a new technique for audio signal comparison based on tonal subsequence alignment and its application to detect cover versions (i.e., different performances of the same underlying musical piece). Cover song identification is a task whose popularity has increased in the Music Information Retrieval (MIR) community along in the past, as it provides a direct and objective way to evaluate music similarity algorithms.This article first presents a series of experiments carried outwith two state-of-the-art methods for cover song identification.We have studied several components of these (such as chroma resolution and similarity, transposition, beat tracking or Dynamic Time Warping constraints), in order to discover which characteristics would be desirable for a competitive cover song identifier. After analyzing many cross-validated results, the importance of these characteristics is discussed, and the best-performing ones are finally applied to the newly proposed method. Multipleevaluations of this one confirm a large increase in identificationaccuracy when comparing it with alternative state-of-the-artapproaches.

A two-stage approach for tonic identification in indian art music

In this paper we propose a new approach for tonic identification in Indian art music and present a proposal for acomplete iterative system for the same. Our method splits the task of tonic pitch identification into two stages. In the first stage, which is applicable to both vocal and instrumental music, we perform a multi-pitch analysis of the audio signal to identify the tonic pitch-class. Multi-pitch analysisallows us to take advantage of the drone sound, which constantlyreinforces the tonic. In the second stage we estimate the octave in which the tonic of the singer lies and is thusneeded only for the vocal performances. We analyse the predominant melody sung by the lead performer in order to establish the tonic octave. Both stages are individually evaluated on a sizable music collection and are shown toobtain a good accuracy. We also discuss the types of errors made by the method.Further, we present a proposal for a system that aims to incrementally utilize all the available data, both audio and metadata in order to identify the tonic pitch. It produces a tonic estimate and a confidence value, and is iterative in nature. At each iteration, more data is fed into the systemuntil the confidence value for the identified tonic is above a defined threshold. Rather than obtain high overall accuracy for our complete database, ultimately our goal is to develop a system which obtains very high accuracy on a subset of the database with maximum confidence.

Applause identification and its relevance to archival of Carnatic music

A Carnatic music concert is made up of a sequence of pieces, where each piece corresponds to a particular genre and ra¯aga (melody). Unlike a western music concert, the artist may be applauded intra-performance inter-performance. Most Carnatic music that is archived today correspond to a single audio recordings of entire concerts.The purpose of this paper is to segment single audio recordings into a sequence of pieces using thecharacteristic features of applause and music. Spectral flux, spectral entropy change quite significantly from music to applause and vice-versa. The characteristics of these features for a subset of concerts was studied. A threshold based approach was used to segment the pieces into music fragments and applauses. Preliminary resultson recordings 19 concerts from matched microphones show that the EER is about 17% for a resolution of 0.25 seconds. Further, a parameter called CUSUM is estimatedfor the applause regions. The CUSUM values determine the strength of the applause. The CUSUM is used to characterise the highlights of a concert.

A method for extracting semantic information from on-line art music discussion forums

In this paper a method for extracting semantic informationfrom online music discussion forums is proposed. The semantic relations are inferred from the co-occurrence of musical concepts in forum posts, using network analysis. The method starts by defining a dictionary of common music terms in an art music tradition. Then, it creates a complex network representation of the online forum by matchingsuch dictionary against the forum posts. Once the complex network is built we can study different network measures, including node relevance, node co-occurrence andterm relations via semantically connecting words. Moreover, we can detect communities of concepts inside the forum posts. The rationale is that some music terms are more related to each other than to other terms. All in all, this methodology allows us to obtain meaningful and relevantinformation from forum discussions.

A Musically aware system for browsing and interacting with audio music collections

In the context of the CompMusic project we are developing methods to automatically describe/annotate audio music recordings pertaining to various music cultures. As away to demonstrate the usefulness of the methods we are also developing a system to browse and interact with specific audio collections. The system is an online web application that interfaces with all the data gathered (audio, scores plus contextual information) and all the descriptions that are automatically generated with the developed methods. In this paper we present the basic architecture of the proposed system, the types of data sources that it includes,and we mention some of the culture specific issues that we are working on for its development. The system is in a preliminary stage but it shows the potential that MIR technologies can have in browsing and interacting with musiccollections of various cultures.

Opportunities for a cultural specific approach in the computational description of music

The current research in Music Information Retrieval (MIR) is showing the potential that the Information Technologies can have in music related applications. Amajor research challenge in that direction is how to automaticallydescribe/annotate audio recordings and how to use the resulting descriptions to discover and appreciate music in new ways. But music is a complex phenomenonand the description of an audio recording has to deal with this complexity. For example, each musicculture has specificities and emphasizes different musicaland communication aspects, thus the musical recordings of each culture should be described differently. At the same time these cultural specificities give us the opportunity to pay attention to musical concepts andfacets that, despite being present in most world musics, are not easily noticed by listeners. In this paper we present some of the work done in the CompMusic project, including ideas and specific examples on how to take advantage of the cultural specificities of differentmusical repertoires. We will use examples from the art music traditions of India, Turkey and China.

Hyperventilation complaints in music performance anxiety among classical music students.

Objective: Despite the importance of respiration and hyperventilation in anxiety disorders, research on breathing disturbances associated with hyperventilation is rare in the field of music performance anxiety (MPA, also known as stage fright). The only comparable study in this area reported a positive correlation between negative feelings of MPA and hyperventilation complaints during performance. The goals of this study were (a) to extend these previous findings to the period before performance, (b) to test whether a positive correlation also exists between hyperventilation complaints and the experience of stage fright as a problem, (c) to investigate instrument-specific symptom reporting, and (d) to confirm gender differences in negative feelings of MPA and hyperventilation complaints reported in other studies. Methods: We assessed 169 university students of classical music with a questionnaire comprising: the State-Trait Anxiety Inventory for negative feelings of MPA, the Nijmegen Questionnaire for hyperventilation complaints, and a single item for the experience of stage fright as a problem. Results: We found a significant positive correlation between hyperventilation complaints and negative feelings of MPA before performance and a significant positive correlation between hyperventilation complaints and the experience of stage fright as a problem. Wind musicians/singers reported a significantly higher frequency of respiratory symptoms than other musicians. Furthermore, women scored significantly higher on hyperventilation complaints and negative feelings of MPA. Conclusion: These results further the findings of previous reports by suggesting that breathing disturbances associated with hyperventilation may play a role in MPA prior to going on stage. Experimental studies are needed to confirm whether hyperventilation complaints associated with negative feelings of MPA manifest themselves at the physiological level. (C) 2010 Elsevier Inc. All rights reserved.

A randomized concave programming method for choice network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing froman offer set, have recently become popular in assortment optimization and revenue management.The dynamic program for these models is intractable and approximated by a deterministiclinear program called the CDLP which has an exponential number of columns. However, whenthe segment consideration sets overlap, the CDLP is difficult to solve. Column generationhas been proposed but finding an entering column has been shown to be NP-hard. In thispaper we propose a new approach called SDCP to solving CDLP based on segments and theirconsideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound onthe dynamic program but coincides with CDLP for the case of non-overlapping segments. Ifthe number of elements in a consideration set for a segment is not very large (SDCP) can beapplied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by(i) simulations, called the randomized concave programming (RCP) method, and (ii) by addingcuts to a recent compact formulation of the problem for a latent multinomial-choice model ofdemand (SBLP+). This latter approach turns out to be very effective, essentially obtainingCDLP value, and excellent revenue performance in simulations, even for overlapping segments.By formulating the problem as a separation problem, we give insight into why CDLP is easyfor the MNL with non-overlapping considerations sets and why generalizations of MNL posedifficulties. We perform numerical simulations to determine the revenue performance of all themethods on reference data sets in the literature.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.

On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

We present a new unifying framework for investigating throughput-WIP(Work-in-Process) optimal control problems in queueing systems,based on reformulating them as linear programming (LP) problems withspecial structure: We show that if a throughput-WIP performance pairin a stochastic system satisfies the Threshold Property we introducein this paper, then we can reformulate the problem of optimizing alinear objective of throughput-WIP performance as a (semi-infinite)LP problem over a polygon with special structure (a thresholdpolygon). The strong structural properties of such polygones explainthe optimality of threshold policies for optimizing linearperformance objectives: their vertices correspond to the performancepairs of threshold policies. We analyze in this framework theversatile input-output queueing intensity control model introduced byChen and Yao (1990), obtaining a variety of new results, including (a)an exact reformulation of the control problem as an LP problem over athreshold polygon; (b) an analytical characterization of the Min WIPfunction (giving the minimum WIP level required to attain a targetthroughput level); (c) an LP Value Decomposition Theorem that relatesthe objective value under an arbitrary policy with that of a giventhreshold policy (thus revealing the LP interpretation of Chen andYao's optimality conditions); (d) diminishing returns and invarianceproperties of throughput-WIP performance, which underlie thresholdoptimality; (e) a unified treatment of the time-discounted andtime-average cases.