An exact algorithm for the network pricing problem

This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved upper bounds, and a column generation procedure for solving the network-structured subproblems. Its efficiency is assessed against both randomly generated instances involving three distinct topologies as well as instances based on real life situations in telecommunication and freight transportation.     

New formulations and valid inequalities for a bilevel pricing problem

Consider the problem of maximizing the toll revenue collected on a multi-commodity transportation network. This fits a bilevel framework where a leader sets tolls, while users respond by selecting cheapest paths to their destination. We propose novel formulations of the problem, together with valid inequalities yielding improved algorithms.     

Editorial: Hierarchical and bilevel programming

Approximately twenty years ago the modern interest for hierarchical programming was initiated by J. Bracken and J.M. McGill [9], [10]. The activities in the field have ever grown lively, both in terms of theoretical developments and terms of the diversity of the applications. The collection of seven papers in this issue covers a diverse number of topics and provides a good picture of recent research activities in the field of bilevel and hierarchical programming. The papers can be roughly divided into three categories; Linear bilevel programming is addressed in the first two papers by Gendreau et al and Moshirvaziri et al; The following three papers by Nicholls, Loridan & Morgan, and Kalashnikov & Kalashnikova are concerned with nonlinear bilevel programming; and, finally, Wen & Lin and Nagase & Aiyoshi address hierarchical decision making issues relating to both biobjective and bilevel programming.     

A bilevel programming approach to the travelling salesman problem

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller-Tucker-Zemlin constraints. Next, we derive an O(n²) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

Finding an efficient solution to linear bilevel programming problem: An effective approach

Multilevel programming is developed to solve the decentralized problem in which decision makers (DMs) are often arranged within a hierarchical administrative structure. The linear bilevel programming (BLP) problem, i.e., a special case of multilevel programming problems with a two level structure, is a set of nested linear optimization problems over polyhedral set of constraints. Two DMs are located at the different hierarchical levels, both controlling one set of decision variables independently, with different and perhaps conflicting objective functions. One of the interesting features of the linear BLP problem is that its solution may not be Paretooptimal. There may exist a feasible solution where one or both levels may increase their objective values without decreasing the objective value of any level. The result from such a system may be economically inadmissible. If the decision makers of the two levels are willing to find an efficient compromise solution, we propose a solution procedure which can generate effcient solutions, without finding the optimal solution in advance. When the near-optimal solution of the BLP problem is used as the reference point for finding the efficient solution, the result can be easily found during the decision process.     

An inexact-restoration method for nonlinear bilevel programming problems

We present a new algorithm for solving bilevel programming problems without reformulating them as single-level nonlinear programming problems. This strategy allows one to take profit of the structure of the lower level optimization problems without using non-differentiable methods. The algorithm is based on the inexact-restoration technique. Under some assumptions on the problem we prove global convergence to feasible points that satisfy the approximate gradient projection (AGP) optimality condition. Computational experiments are presented that encourage the use of this method for general bilevel problems. This work was supported by PRONEX-Optimization (PRONEX—CNPq/FAPERJ E-26/171.164/2003—APQ1), FAPESP (Grants 06/53768-0 and 05-56773-1) and CNPq.     

An Attractor-Repeller approach to floorplanning

The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying height and width) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard combinatorial optimization problem; even the restricted version where the shapes of the modules are fixed and the optimization is taken over a fixed finite set of possible module locations is NP-hard. In this paper, we extend the concept of target distance introduced by Etawil and Vannelli and apply it to derive the AR (Attractor-Repeller) model which is designed to improve upon the NLT method of van Camp et al. This new model is designed to find a good initial point for the Stage-3 NLT solver and has the advantage that it can be solved very efficiently using a suitable optimization algorithm. Because the AR model is not a convex optimization problem, we also derive a convex version of the model and explore the generalized target distances that arise in this derivation. Computational results demonstrating the potential of our approach are presented.     

交叉规划与双层规划的经济背景差异分析

本文分析了交叉规划问题与双层规划问题的实际经济背景,重点讨论了这两类问题解之间的不同经济意义．指出双层规划刻画的是两个经济行为人之间的主从属关系,而交叉规划刻画的则是两个经济行为人之间的平等互利关系     

Dynamic pricing of electricity in retail markets

This paper aims at defining a dynamic and flexible tariff structure for a distribution company that protects the retail consumers against the excessive fluctuations of the wholesales market prices. We propose a two-stage pricing scheme that sets in a first-stage a time-of-use tariff that is corrected later by a dynamic component once the real-time demand has been observed. A personalized tariff scheme may be offered by a distribution company to each dynamic customer by allowing him to choose the appropriate robustness level expressed in terms of variability between the first and the second-stage decisions. The arising limited recourse model has been tested on realistic test problems, by using a slight modification of a recently proposed interior point solution framework.      

Nonlinear programming methods in the presence of noise

The problem of minimizing a nonlinear function with nonlinear constraints when the values of the objective, the constraints and their gradients have errors, is studied. This noise may be due to the stochastic nature of the problem or to numerical error.Various previously proposed methods are reviewed. Generally, the minimization algorithms involve methods of subgradient optimization, with the constraints introduced through penalty, Lagrange, or extended Lagrange functions. Probabilistic convergence theorems are obtained. Finally, an algorithm to solve the general convex (nondifferentiable) programming problem with noise is proposed.Originally written for presentation at the 1976 Budapest Symposium on Mathematical Programming.     

An inexact approach to solving linear semi-infinite programming problems

In this paper, we propose an “inexact solution” approach to deal with linear semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. A general convergence proof with some numerical examples are given and the advantages of using this approach are discussed     

Multicriteria integer programming: A (hybrid) dynamic programming recursive approach

Dynamic programming recursive equations are used to develop a procedure to obtain the set of efficient solutions to the multicriteria integer linear programming problem. An alternate method is produced by combining this procedure with branch and bound rules. Computational results are reported.     

一类特殊线性双层规划的对偶规划

本文首先给出值型线性双层规划的等价形式 ,然后讨论了非增的值型线性双层规划的 Johri一般对偶规划 ,并且说明了其对偶间隙等于零 ,最后说明了它们最优解的关系     

An Optimal Congestion and Cost-sharing Pricing Scheme for Multiclass Services

We study in this paper a social welfare optimal congestion-pricing scheme for multiclass queuing services which can be applied to telecommunication networks. Most of the literature has focused on the marginal price. Unfortunately, it does not share the total cost among the different classes. We investigate here an optimal Aumann–Shapley congestion-price which verifies this property. We extend the work on the Aumann–Shapley price for priority services, based on the results on the marginal price: instead of just determining the cost repartition among classes for given rates, we obtain the rates and charges that optimize the social welfare.     

A survey of some mathematical programming models in transportation

Transportation problems constitute a fertile domain for the application of mathematical programming models and nonlinear optimization techniques, distribution problems, entropy models, traffic assigment problems and many others are good examples of this assertion. This paper provides a summary overview of the main modeling approaches in transportation and the related optimization models, symmetric and asymmetric, and an overview on the state-of-the-art of the origindestination adjustment problems and the related bilevel optimization methods.     

NP组合优化近似计算的难度

本文扼要介绍近二十年来在组合优化可近似性的研究方面所取得的进展,包括不可近似性的证明,对组合优化问题用逻辑描述的语法分类及其可近似性．     

Model and extended Kuhn–Tucker approach for bilevel multi-follower decision making in a referential-uncooperative situation

When multiple followers are involved in a bilevel decision problem, the leader’s decision will be affected, not only by the reactions of these followers, but also by the relationships among these followers. One of the popular situations within this bilevel multi-follower issue is where these followers are uncooperatively making their decisions while having cross reference to decision information of the other followers. This situation is called a referential-uncooperative situation in this paper. The well-known Kuhn–Tucker approach has been previously successfully applied to a one-leader-and-one-follower linear bilevel decision problem. This paper extends this approach to deal with the above-mentioned linear referential-uncooperative bilevel multi-follower decision problem. The paper first presents a decision model for this problem. It then proposes an extended Kuhn–Tucker approach to solve this problem. Finally, a numerical example illustrates the application of the extended Kuhn–Tucker approach.