1,720,979 research outputs found
Optimal Assignment of High Multiplicity Flight Plans to Dispatchers
No full textThis paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP-complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real-life instances
Computational study of separation algorithms for clique inequalities
No full textClique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics
The stable set problem: Clique and nodal inequalities revisited
Full text linkThe stable set problem is a fundamental combinatorial optimisation problem, that is known to be very difficult in both theory and practice. Some of the solution algorithms in the literature are based on 0-1 linear programming formulations. We examine an entire family of such formulations, based on so-called clique and nodal inequalities. As well as proving some theoretical results, we conduct extensive computational experiments. This enables us to derive guidelines on how to choose the right formulation for a given instance
A Time Indexed Formulation for Scheduling Commands on a Satellite Constellation
No full textIn this paper we describe a space application concerning the scheduling of command transmissions on a satellite constellation. The central controller has to decide the allocation of radio-messages to terrestrial base stations and their transmission times to the satellites, so as to minimize the number of unscheduled messages. In this work we investigate the computational behavior of a time indexed formulation that is able to model several different constraints arising from the application. Unlike random generated instances, large real-world instances are solved in a reasonable amount of time in a branch-and-cut framework
A tight reformulation of the power-and-frequency assignment problem in wireless networks
No full textOne major task in wireless network planning is to assign emission powers and frequencies to transmitters so as to maximize the customers coverage (Power and Frequency Assignment Problem, PFAP). We present an optimization model which can be applied whenever the coverage is evaluated through a ̄nite set of testpoints, and the coverage condition of one testpoint can be cast into a linear function of the wanted and interfering signals. This happens, for instance, in mobile telephony and audio/video broadcasting. Natural compact integer programming formulations for PFAP often show large integrality gap and cannot be used to solve instances of practical interest. We present a non-compact Set Packing formulation for PFAP obtained by applying the Dantzig-Wolfe decomposition to the natural formulation. The pricing problem consists in optimizing the emission powers in a single frequency network, for which effective algorithms are available. Experiments show that the non-compact formulation is very tight and the resulting branch-and-price algorithm solves to optimality practically relevant instances of the Italian broadcasting system
- …
