Upper and lower bounds for the fixed spectrum frequency assignment problem

A survey of the results described in the authors PhD thesis (Montemanni 2001) is presented. The thesis, which was supervised by Prof. Derek H. Smith and Dr. Stuart M. Allen, has been defended in January 2002 at the University of Glamorgan (U.K.). The thesis proposes new heuristic algorithms, based on well-known meta-heuristic paradigms, and new lower bounding techniques, based on linear programming, for the fixed spectrum frequency assignment problem.Received: May 2003, Revised: May 2003, AMS classification: 90C27, 90C59,05C90, 90C05Roberto Montemanni: Present address: Istituto Dalle Molle di Studi sullIntelligenza Artificiale (IDSIA), Galleria 2, 6928 Manno-Lugano, Switzerland (e-mail: roberto@idsia.ch)     

Dealing with inconsistent judgments in multiple criteria sorting models

Sorting models consist in assigning alternatives evaluated on several criteria to ordered categories. To implement such models it is necessary to set the values of the preference parameters used in the model. Rather than fixing the values of these parameters directly, a usual approach is to infer these values from assignment examples provided by the decision maker (DM), i.e., alternatives for which (s)he specifies a required category. However, assignment examples provided by DMs can be inconsistent, i.e., may not match the sorting model. In such situations, it is necessary to support the DMs in the resolution of this inconsistency. In this paper, we extend algorithms from mous5ejor03 that calculate different ways to remove assignment examples so that the information can be represented in the sorting model. The extension concerns the possibility to relax (rather than to delete) assignment examples. These algorithms incorporate information about the confidence attached to each assignment example, hence providing inconsistency resolutions that the DMs are most likely to accept. Received: September 2004, Revised: June 2005 AMS classification: 90B50, 91B08, 90C05     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

多无线WMN中干扰最小化信道分配算法研究

为了提高无线迈适网的通信容量,网络中的每个路由节点均配备有多个无线网卡,并提供多个可用的无线信道.如何将这些信道合理地分配到网络的各个通信链路上,使得整个网络的干扰最小是一个至关重要问题.分析了基于禁忌搜索的信道分配算法,并针对该算法存在的问题,提出了初步的改进算法.     

Random assignment problems

Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem’s solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems. This paper presents an overview of the recent results and developments in the area of probabilistic assignment problems, including the linear and multidimensional assignment problems, quadratic assignment problem, etc.     

Fixed interval scheduling: Models,applications, computational complexity and algorithms

The defining characteristic of fixed interval scheduling problems is that each job has a finite number of fixed processing intervals. A job can be processed only in one of its intervals on one of the available machines, or is not processed at all. A decision has to be made about a subset of the jobs to be processed and their assignment to the processing intervals such that the intervals on the same machine do not intersect. These problems arise naturally in different real-life operations planning situations, including the assignment of transports to loading/unloading terminals, work planning for personnel, computer wiring, bandwidth allocation of communication channels, printed circuit board manufacturing, gene identification and examining computer memory structures. We present a general formulation of the interval scheduling problem, show its relations to cognate problems in graph theory, and survey existing models, results on computational complexity and solution algorithms.     

Robust Capacity Assignment in Telecommunications

In telecommunications, the demand is a key data that drives network planning. The demand exhibits considerable variability, due to customers movement and introduction of new services and products in the present competitive markets. To deal with this uncertainty, we consider capacity assignment problem in telecommunications in the framework of robust optimization proposed in Ben-Tal and Nemcrovski (Math Oper Res 23(4):769–805, 1998, MPS-SIAM series on optimization, 2001) and Kouvelis and Yu. We propose a decomposition scheme based on cutting plane methods. Some preliminary computational experiments indicate that the Elzinga–Moore cutting plane method (Elzinga and Moore in Math Program 8:134–145, 1975) can be a valuable choice. Since in some situations different possible uncertainty sets may exist, we propose a generalization of these models to cope at a time with a finite number of plausible uncertainty sets. A weight is associated with each uncertainty set to determine its relative importance or worth against another.     

Lower bounding and tabu search procedures for the frequency assignment problem with polarization constraints

The problem retained for the ROADEF’2001 international challenge was a Frequency Assignment Problem with polarization constraints (FAPP). This NP-hard problem was proposed by the CELAR of the French Department of Defense, within the context of the CALMA project. Twenty seven competitors took part to this contest, and we present in this paper the contribution of our team that allowed us to be selected as one of the six finalists qualified for the final round of the competition.There is typically no solution satisfying all constraints of the FAPP. For this reason, some electromagnetic compatibility constraints can be progressively relaxed, and the objective is to find a feasible solution with the lowest possible level of relaxation. We have developed a procedure that computes a lower bound on the best possible level of relaxation, as well as two tabu search algorithms for the FAPP, one for the frequency assignment, and one for the polarization assignment.Received: July 2003, Revised: October 2004, AMS classification: 90C27, 90C35, 90C59Alain Hertz: Correspondence to     

Trust-region algorithms for derivative-free optimization and nonlinear bilevel programming

We briefly describe the contents of the authors PhD thesis (see Colson 2003) discussed on July 2003 at the University of Namur (Belgium) and supervised by Philippe L. Toint. The contributions presented in this thesis are the development of trust-region methods for solving two particular classes of mathematical programs, namely derivative-free optimization (DFO) problems and nonlinear bilevel programming problems. The thesis is written in English and is available via the author.Received: July 2003, AMS classification: 65D05, 90C30, 90C56, 90C59     

LP formulations of the shortest path tree problem

Based on a pair of primal-dual LP formulations of the shortest path tree problem, the first algorithmic approach to reoptimizing the shortest paths subject to changes in the edge weights was proposed by S. Pallottino and M.G. Scutellá in 2003. We shall here focus solely on their introductory sections, propose some simplifications of the models considered, and finally relate the resulting models to the presentation of single-source shortest path problems in textbooks treating this subject with but limited or no reference to LP.Received: April 2004, Revised: August 2004, MSC classification: 90C05, 90C35, 90B10 Dedicated to the memory of Stefano Pallottino     

Using fuzzy integral for evaluating subjectively perceived travel costs in a traffic assignment model

A good traffic assignment model can be a powerful tool to describe the characteristics of traffic behavior in a road network. The traffic assignment results often play an important role in transportation planning, e.g., an optimal and economical network design. Many traditional traffic assignment models rely heavily on the travel cost function established by Wardrop’s principles; however, the Wardrop’s travel cost function has been proven to be weak for explaining the uncertainty and interactivity of traffic among links. This study tries to construct a traffic assignment model that is different from Wardrop’s in many aspects. First, it considers the cross-effect among the links. Second, a fuzzy travel cost function is established based on the possibility concept instead of precise calculation of traffic volumes. Third, the techniques of fuzzy measure and fuzzy integral are applied to calculate the subjectively perceived travel costs during traffic assignment. Furthermore, in order to validate our model, a detailed network with 22 nodes and 36 links is used to illustrate it. Study results show that our model explains more interactivity and uncertainty of traffic among links when compared with the traditional model of Wardrop’s.     

Stochastic programming with integer variables

 Including integer variables into traditional stochastic linear programs has considerable implications for structural analysis and algorithm design. Starting from mean-risk approaches with different risk measures we identify corresponding two- and multi-stage stochastic integer programs that are large-scale block-structured mixed-integer linear programs if the underlying probability distributions are discrete. We highlight the role of mixed-integer value functions for structure and stability of stochastic integer programs. When applied to the block structures in stochastic integer programming, well known algorithmic principles such as branch-and-bound, Lagrangian relaxation, or cutting plane methods open up new directions of research. We review existing results in the field and indicate departure points for their extension. Received: December 2, 2002 / Accepted: April 23, 2003 Published online: May 28, 2003 Mathematics Subject Classification (2000): 90C15, 90C11, 90C06, 90C57     

Design issues for combinatorial auctions

Combinatorial auctions are an important class of market mechanisms in which participants are allowed to bid on bundles of multiple heterogeneous items. In this paper, we discuss several complex issues that are encountered in the design of combinatorial auctions. These issues are related to the formulation of the winner determination problem, the expression of combined bids, the design of progressive combinatorial auctions that require less information revelation, and the need for decision support tools to help participants make profitable bidding decisions. For each issue, we survey the existing literature and propose avenues for further research.Received: April 2003, Revised: July 2003, AMS classification: 91B26, 90BXX, 90C27All correspondence to:Jawad Abrache     

Minimum convex piecewise linear cost tension problem on quasi-<Emphasis Type="Italic">k</Emphasis> series-parallel graphs

Some hypermedia synchronization issues request the resolution of the minimum convex piecewise linear cost tension problem (CPLCT problem) on directed graphs that are close to two-terminal series-parallel graphs (TTSP-graphs), the so-called quasi-k series-parallel graphs (k-QSP graphs). An aggregation algorithm has already been introduced for the CPLCT problem on TTSP-graphs. We propose here a reconstruction method, based on the aggregation and the well-known out-of-kilter techniques, to solve the problem on k-QSP graphs. One of the main steps being to decompose a graph into TTSP-subgraphs, methods based on the recognition of TTSP-graphs are thoroughly discussed.Received: October 2003, Revised: July 2004, MSC classification: 90C35, 05C85     

Constrained auction clearing in the Italian electricity market

Most of the liberalized electricity systems use the auction as a market model. The complexity of the underlying optimization formulation depends on the technical and regulatory constraints that must be considered. In Italy, the auction clearing should include not only congestion management limitations, but also a challenging regulatory constraint imposing that, while the zonal prices are allowed on the selling side, a uniform purchasing price has to be applied for all the zones of the Italian system. Such constraint introduces several complexities such as non-linearity and integrality. In this paper we discuss the modeling issues arising in the Italian context and we propose, in addition, a mechanism for the priority management of the offers/bids acceptance. We test the behavior of the models developed on a set of problems that represent all the possible scenarios that can be met in practice. The numerical results demonstrate the validity and the effectiveness of the proposed models.Received: May 2003 , Revised : November 2003, AMS classification: 90-20, 90C90     

The dynamic frequency assignment problem

In this paper, we consider a frequency assignment problem occurring in a military context. The main originality of the problem pertains to its dynamic dimension: new communications requiring frequency assignments need to be established throughout a battlefield deployment. The problem resolution framework decomposes into three phases: assignment of an initial kernel of communications, dynamic assignment of new communication links and a repair process when no assignment is possible. Different solution methods are proposed and extensive computational experiments are carried out on realistic instances.     

Two-level fractional factorial designs in blocks of size two for the orthogonal estimation of all main effects and two-factor interactions

In this paper we consider the problem of constructing two-level fractional factorial designs in blocks of size two that allow for the orthogonal estimation of all main effects and two-factor interactions (after adjusting for blocks). This problem has been considered in the literature, e.g., see Yang and Draper (2003), Wang (2004) and Kerr (2006). In this paper we give two systematic methods for the construction of such designs. The first construction method gives in many situations designs requiring fewer runs than those designs previously given whereas the second method gives a systematic method for constructing designs analogous to those illustrated in Yang and Draper (2003) by example.