Search

In this paper, by resorting to classical methods of statistical mechanics, we build a kinetic model able to reproduce the observed statistical weight distribution of many diverse species. The kinetic description of the time variations of the weight distribution is based on elementary interactions that describe in a qualitative and quantitative way successive evolutionary updates, and determine explicit equilibrium distributions. Numerical fittings on mammalian eutherians of the order Chiroptera population illustrates the effectiveness of the approach.

A total coloring of a graph $G = (V, E)$ is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the elements of $G$ into total matchings, which are defined as subsets of vertices and edges that can take the same color. In this paper, we propose Integer Linear Programming models for both the Total Coloring and the Total Matching problems, and we study the strength of the corresponding Linear Programming relaxations. The total coloring is formulated as the problem of finding the minimum number of total matchings that cover all the graph elements. This covering formulation can be solved by a Column Generation algorithm, where the pricing subproblem corresponds to the Weighted Total Matching Problem. Hence, we study the Total Matching Polytope. We introduce three families of nontrivial valid inequalities: vertex-clique inequalities based on standard clique inequalities of the Stable Set Polytope, congruent-$2k3$ cycle inequalities based on the parity of the vertex set induced by the cycle, and even-clique inequalities induced by complete subgraphs of even order. We prove that congruent-$2k3$ cycle inequalities are facet-defining only when $k = 4$, while the vertex-clique and even-cliques are always facet-defining. Finally, we present preliminary computational results of a Column Generation algorithm for the Total Coloring Problem and a Cutting Plane algorithm for the Total Matching Problem., Comment: 29 pages, 5 figures

In the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is [Formula: see text]-hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovász’s Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub.

We present a kinetic approach to the formation of urban agglomerations which is based on simple rules of immigration and emigration. In most cases, the Boltzmann-type kinetic description allows to obtain, within an asymptotic procedure, a Fokker–Planck equation with variable coefficients of diffusion and drift, which describes the evolution in time of some probability density of the city size. It is shown that, in dependence of the microscopic rules of migration, the equilibrium density can follow both a power law for large values of the size variable, which contains as particular case a Zipf’s law behavior, and a lognormal law for middle and low values of the size variable. In particular, connections between the value of Pareto index of the power law at equilibrium and the disposal of the population to emigration are outlined. The theoretical findings are tested with recent data of the populations of Italy and Switzerland.

In recent years, it has been increasing evidence that lognormal distributions are widespread in physical and biological sciences, as well as in various phenomena of economics and social sciences. In social sciences, the appearance of lognormal distribution has been noticed, among others, when looking at body weight, and at women’s age at first marriage. Likewise, in economics, lognormal distribution appears when looking at consumption in a western society, at call-center service times, and others. The common feature of these situations, which describe the distribution of a certain people’s hallmark, is the presence of a desired target to be reached by repeated choices. In this paper, we discuss a possible explanation of lognormal distribution forming in human activities by resorting to classical methods of statistical mechanics of multi-agent systems. The microscopic variation of the hallmark around its target value, leading to a linear Fokker–Planck-type equation with lognormal equilibrium density, is built up introducing as main criterion for decision a suitable value function in the spirit of the prospect theory of Kahneman and Twersky.

We investigate properties of some extensions of a class of Fourier-based probability metrics, originally introduced to study convergence to equilibrium for the solution to the spatially homogeneous Boltzmann equation. At difference with the original one, the new Fourier-based metrics are well-defined also for probability distributions with different centers of mass, and for discrete probability measures supported over a regular grid. Among other properties, it is shown that, in the discrete setting, these new Fourier-based metrics are equivalent either to the Euclidean-Wasserstein distance $W_2$, or to the Kantorovich-Wasserstein distance $W_1$, with explicit constants of equivalence. Numerical results then show that in benchmark problems of image processing, Fourier metrics provide a better runtime with respect to Wasserstein ones., Comment: 18 pages, 2 figures, 1 table

In this work, we present a method to compute the Kantorovich--Wasserstein distance of order 1 between a pair of two-dimensional histograms. Recent works in computer vision and machine learning have...

We consider the problem of allocating students to project topics satisfying side constraints and taking into account students’ preferences. Students rank projects according to their preferences for the topic and side constraints limit the possibilities to team up students in the project topics. The goal is to find assignments that are fair and that maximize the collective satisfaction. Moreover, we consider issues of stability and envy from the students’ viewpoint. This problem arises as a crucial activity in the organization of a first year course at the Faculty of Science of the University of Southern Denmark. We formalize the student-project allocation problem as a mixed integer linear programming problem and focus on different ways to model fairness and utilitarian principles. On the basis of real-world data, we compare empirically the quality of the allocations found by the different models and the computational effort to find solutions by means of a state-of-the-art commercial solver. We provide empirical evidence about the effects of these models on the distribution of the student assignments, which could be valuable input for policy makers in similar settings. Building on these results we propose novel combinations of the models that, for our case, attain feasible, stable, fair and collectively satisfactory solutions within a minute of computation. Since 2010, these solutions are used in practice at our institution.

We present a new Linear Programming model that formulates the problem of computing the Kantorovich-Wasserstein distance associated with a truncated ground distance. The key idea of our model is to consider only the quantity of mass that is transported to nearby points and to ignore the quantity of mass that should be transported between faraway pairs of locations. The proposed model has a number of variables that depends on the threshold value used in the definition of the set of nearby points. Using a small threshold value, we can obtain a significant speedup. We use our model to numerically evaluate the percentage gap between the true Wasserstein distance and the truncated Wasserstein distance, using a set of standard grey scale images.

In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem (AQTSP). Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimal. We propose an extended Linear Programming formulation that has a variable for each cycle in the graph. Since the number of cycles is exponential in the graph size, we propose a column generation approach. Moreover, we apply a particular reformulation-linearization technique on a compact representation of the problem, and compute lower bounds based on Lagrangian relaxation. We compare our new bounds with those obtained by some linearization models proposed in the literature. Computational results on some set of benchmarks used in the literature show that our lower bounding procedures are very promising.

Call centers are service networks in which agents provide telephone-based services. An important part of call center operations is represented by service durations. In recent statistical analysis of real data, it has been noted that the distribution of service times reveals a remarkable fit to the lognormal distribution. In this paper, we discuss a possible source of this behavior by resorting to classical methods of statistical mechanics of multi-agent systems. The microscopic service time variation leading to a linear kinetic equation with lognormal equilibrium density is built up introducing as main criterion for decision a suitable value function in the spirit of the prospect theory of Kahneman and Twersky.

This paper discusses a new method to perform propagation over a (two-layer, feed-forward) Neural Network embedded in a Constraint Programming model. The method is meant to be employed in Empirical Model Learning, a technique designed to enable optimal decision making over systems that cannot be modeled via conventional declarative means. The key step in Empirical Model Learning is to embed a Machine Learning model into a combinatorial model. It has been showed that Neural Networks can be embedded in a Constraint Programming model by simply encoding each neuron as a global constraint, which is then propagated individually. Unfortunately, this decomposition approach may lead to weak bounds. To overcome such limitation, we propose a new network-level propagator based on a non-linear Lagrangian relaxation that is solved with a subgradient algorithm. The method proved capable of dramatically reducing the search tree size on a thermal-aware dispatching problem on multicore CPUs. The overhead for optimizing the Lagrangian multipliers is kept within a reasonable level via a few simple techniques. This paper is an extended version of [27], featuring an improved structure, a new filtering technique for the network inputs, a set of overhead reduction techniques, and a thorough experimentation.

The Production Scheduling is an important phase in a manufacturing system, where the aim is to improve the productivity of one or more factories. Finding an optimal solution to scheduling problems means to approach complex combinatorial optimization problems, and not all of them are solvable in a mathematical way, in fact a lot of them are part of the class of NP-hard combinatorial problems. In this paper a joint mixed approach based on a joint use of Evolutionary Algorithms and their quantum version is proposed. The context is ideally located inside two factories, partners and use cases of the white’R FP7 FOF MNP Project, with high manual activity for the production of optoelectronics products, switching with the use of the new robotic (re)configurable island, the white’R, to highly automated production. This is the first paper approaching the problem of the dynamic production scheduling for these types of production systems proposing a cooperative solving method. Results show this mixed method provide better answers and is faster in convergence than others.

BACKGROUND: Esophago-gastrointestinal symptoms are frequently reported by patients with eating disorders. Scanty data exist on the relationship between psychopathological traits and digestive complaints. AIMS: To prospectively analyze (i) prevalence of digestive symptoms; (ii) psychopathological traits; (iii) relationship between symptom scores and psychopathological profiles. METHODS: Psychopathological and digestive symptom questionnaires were completed at baseline, at discharge, at 1 and 6 months' follow-up in 48 consecutive patients (85.4% female, median age, 15 years) hospitalized for eating disorders. RESULTS: The most frequently reported symptoms were postprandial fullness (96%) and abdominal distention (90%). Pooled esophageal (4; IQR 0-14) and gastrointestinal (34; IQR 19-53) symptoms significantly decreased at 6 months' follow-up (1; IQR 0-3 and 10; IQR 4-34; p

Given a bipartite graph G = (S, T, E), we consider the problem of finding k bipartite subgraphs, called ”clusters”, such that each vertex i of S appears in exactly one of them, every vertex j of T appears in each cluster in which at least one of its neighbors appears, and the total number of edges needed to make each cluster complete (i.e., to become a biclique) is minimized. This problem is known as k-clustering Minimum Biclique Completion Problem and has been shown strongly NP-hard. It has applications in bundling channels for multicast transmissions. Given a set of demands of services from clients, the application consists of findin g k multicast sessions that partition the set of demands. Each service has to belong to a single multicast session, while ea ch client can appear in more sessions. We extend previous work by developing a Branch and Price algorithm that embeds a new metaheuristic based on Variable Neighborhood Infeasible Search and a non-trivial branching rule. The metaheuristic is also adapted to solve effi ciently the pricing subproblem. In addition to the random instances used in the literature, we present structured instances generated usin g the MovieLens data set collected by the GroupLens Research Project. Extensive computational results show that our Branch and Price algorithm outperforms the approaches proposed in the literature.

We consider two approaches for solving the classical minimum vertex coloring problem—that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors—namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but suffers from a lack of effective bounding methods. On the contrary, column generation provides tight lower bounds by solving the fractional vertex coloring problem exploited in a branch-and-price algorithm, as already proposed in the literature. The column generation approach is here enhanced by using constraint programming to solve the pricing subproblem and to compute heuristic solutions. Moreover, new techniques are introduced to improve the performance of the column generation approach in solving both the linear relaxation and the integer problem. We report extensive computational results applied to the benchmark instances: we are able to prove optimality of 11 new instances and to improve the best-known lower bounds on 17 other instances. Moreover, we extend the solution approaches to a generalization of the problem known as the minimum vertex graph multicoloring problem, where a given number of colors has to be assigned to each vertex.

We present a branching scheme for some vertex coloring problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as graph multicoloring, where each vertex requires a multiplicity of colors, graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, which generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the effectiveness of the new branching scheme.

A fundamental and computationally challenging optimization task in wireless networks is to maximize the number of simultaneous transmissions, subject to signal-to-noise-and-interference ratio (SINR) requirements at the receivers. The conventional approach guaranteeing global optimality is to solve an integer programming model with explicit SINR constraints. These constraints are however numerically very difficult. We develop a new integer programming algorithm based on a much more effective representation of the SINR constraints. Computational experiments demonstrate that the new approach performs significantly better in proving optimality. ©2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. Antonio Capone, Lei Chen, Stefano Gualandi and Di Yuan, A New Computational Approach for Maximum Link Activation in Wireless Networks under the SINR Model, 2011, IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, (10), 5, 1368-1372. http://dx.doi.org/10.1109/TWC.2011.030311.100777

Objective This study evaluates the psychometric properties of self-administered psychiatric scale for children and adolescents with psychogenic eating disorders (SAFA P)—a brief self-report designed to screen and assess eating disorders (ED) in children and adolescents. Although SAFA P belongs to a broad battery of tests (SAFA) that explores different psychiatric conditions, it has not undergone appropriate validation until now. Method We administered SAFA P and Eating Disorder Inventory 2 (EDI-2) to 87 ED patients, with an average age of 15.4 ± 1.6 years. Results The internal reliability of SAFA P is good (Cronbach α = .776). Convergent validity with EDI-2 was assessed: both SAFA P subscale P1 (p

OBJECTIVE To evaluate the frequency of normalization, the persistence of remission, and the impact on normalization of glycemic control and lipid profile, we analyzed data from a retrospective observational cohort study of type 1 diabetic children and adolescents with abnormal urinary albumin excretion (UAE). RESEARCH DESIGN AND METHODS All diabetic children and adolescents (n = 41) who had persistent abnormal UAE in the period of 1984 to 2008 and followed up until 2009 (follow-up duration = 13.1 ± 6.2 years) were included in the study. Nine patients progressed to macroalbuminuria; 24 patients were administered ACE inhibitor treatment. RESULTS The cumulative prevalence of abnormal UAE was 9%. During follow-up, 14 of 17 untreated and 19 of 24 treated patients reverted to normoalbuminuria. In the remission group compared with the nonremission group, A1C levels during follow-up decreased (7.5 ± 1.0 vs. 9.4 ± 1.2%, P < 0.0001) and serum HDL cholesterol increased (52.7 ± 11.3 vs. 42.7 ± 8.6 mg/dL, P < 0.05). The micro-macroalbuminuric patients had lower HDL cholesterol (51.0 ± 11.4 vs. 62.4 ± 13.6 mg/dL, P < 0.0001) than 134 normoalbuminuric diabetic patients. CONCLUSIONS Microalbuminuria and macroalbuminuria were not permanent in most of our diabetic children and adolescents. If abnormal UAE values are high and persist for >1 year, only long-lasting treatment with ACE inhibitors seems able to induce persistent remission, especially when associated with good metabolic control and high HDL cholesterol levels.

We consider the problem of spanning the nodes of a given colored graph G=(N,A) by a set of node-disjoint cycles at minimum reload cost, where a non-negative reload cost is paid whenever passing through a node where the two consecutive arcs have different colors. We call this problem Minimum Reload Cost Cycle Cover (MinRC3 for short). We prove that it is strongly NP-hard and not approximable within 1@e for any @e>0 even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. Some IP models for MinRC3 are then presented, one well suited for a Column Generation approach. The corresponding pricing subproblem is also proved strongly NP-hard. Primal bounds for MinRC3 are obtained via local search based heuristics exploiting 2-opt and 3-opt neighborhoods. Computational results are presented comparing lower and upper bounds obtained by the above mentioned approaches.