用线性互补及二次规划理论分析市场均衡问题

本文讨论了一类完全竞争条件下的市场均衡问题,供给方的生产特征用线性规划模型进行刻划,市场需求函数源于一般经济意义下的模型,它是一系列相互独立的价格变量的函数．我们将此问题归结为线性互补问题,并依此讨论了均衡点的存在性．本文还讨论了一种用二次规划进行刻划的经济问题,并指出此二次规划的K－K－T条件等价于所讨论的线性互补问题．     

A unifying framework for duality and modeling in robust linear programs

In this paper, our major theme is a unifying framework for duality in robust linear programming. We show that there are two pair of dual programs allied with a robust linear program; one in which the primal is constructed to be “ultra-conservative” and one in which the primal is constructed to be “ultra-optimistic.” Furthermore, as one would expect, if the uncertainly in the primal is row-based, the corresponding uncertainty in the dual is column-based, and vice-versa. Several examples are provided that illustrate the properties of these primal and dual models.     

弹性需求下网络设计问题和电子路票问题研究

应用双(二)层规划模型研究弹性需求下网络设计问题与电子路票收取问题,其中只考虑在部分路段进行路段能力扩充和收取电子路票.上层决策者(网络规划者)选择路段能力增加和收取电子路票的数量来获得最优的社会总福利.下层决策者(网络用户)选择路径来最小化他们的出行成本(路径出行时间与所付出电子路票的价值的和).应用下层规划问题的Ka-rush-Kuhn-Tucker(KKT)条件,将双层规划模型转化为单层规划模型.为了解决互补条件所造成的求解困难,本文构造了松弛算法进行求解,并用数值试验研究了模型和算法的可行性.数值结果表明,本文的模型在缓解交通拥挤方面可以得到更好的效果,而且只在部分路段进行路段能力扩充和收取电子路票更加方便实用.在可交易电子路票方案中,更多出行的用户需要购买电子路票来为他们的额外出行付费,而减少出行的用户则可以卖出多余电子路票得到补偿,同时电子路票的交易价格是在完全竞争的市场上形成的,因此本文中的可交易电子路票机制是收入中性的.     

The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach

In this paper, we consider a variant of the Location-Routing Problem (LRP), namely the LRP with simultaneous pickup and delivery (LRPSPD). The LRPSPD seeks to minimize total cost by simultaneously locating the depots and designing the vehicle routes that satisfy pickup and delivery demand of each customer at the same time. We propose two polynomial-size mixed integer linear programming formulations for the problem and a family of valid inequalities to strengthen the formulations. While the first formulation is a node-based formulation, the second one is a flow-based formulation. Furthermore, we propose a two-phase heuristic approach based on simulated annealing, tp_SA, to solve the large-size LRPSPD and two initialization heuristics to generate an initial solution for the tp_SA. We then empirically evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions or strong lower bounds, and investigate the performance of the proposed heuristic approach. Computational results show that the flow-based formulation performs better than the node-based formulation in terms of the solution quality and the computation time on small-size problems. However, the node-based formulation can yield competitive lower bounds in a reasonable amount of time on medium-size problems. Meantime, the proposed heuristic approach is computationally efficient in finding good quality solutions for the LRPSPD.     

Duality of the improved algebraic method (DIAM)

In this note we present a variant of the improved algebraic method (IAM) using a duality analysis to solve linear programming (LP) problems where more insights to the method are presented. When the coordinates of all vertices are computed, any feasible point can be expressed as a linear combination of the vertices. The objective function is expressed as a weighted sum of its evaluation at the feasible vertices and the optimal point is associated with the highest/lowest coefficient of the weighted sum.     

漂移型线性规划理论及应用

到目前为止,有关灰色线性规划问题有不少研究,如灰色预测型线性规划^[1～6]灰色区间型线性规划^[7]等．本文在文献^[1～7]的基础上,针对漂移型线性规划问题,运用参数线性规划理论与方法,对其满意解及其性质等进行探研,并提出了一些新的结论,不仅为漂移型线性规划作了一些理论讨论,而且还以应用实例给予示范．     

Approximate solution of a profit maximization constrained virtual business planning problem

A virtual business problem is studied, in which a company-contractor outsources production to specialized subcontractors. Finances of the contractor and resource capacities of subcontractors are limited. The objective is to select subcontractors and distribute a part of the demanded production among them so that the profit of the contractor is maximized. A generalization of the knapsack problem, called Knapsack-of-Knapsacks (K-of-K), is used to model this situation, in which items have to be packed into small knapsacks and small knapsacks have to be packed into a large knapsack. A fully polynomial time approximation scheme is developed to solve the problem K-of-K.     

An access network design problem with end-to-end QoS constraints

In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.     

Two-stage time minimizing assignment problem

This paper deals with the optimal selection of m out of n facilities to first perform m   given primary jobs in Stage-I followed by the remaining (n-m)$(n-m)$ facilities performing optimally the (n-m)$(n-m)$ secondary jobs in Stage-II. It is assumed that in both the stages facilities perform in parallel. The aim of the proposed study is to find that set of m   facilities performing the primary jobs in Stage-I for which the sum of the overall completion times of jobs in Stage-I and the corresponding optimal completion time of the secondary jobs in Stage-II by the remaining (n-m)$(n-m)$ facilities is the minimum. The developed solution methodology involves solving the standard time minimizing and cost minimizing assignment problems alternately after forbidding some facility-job pairings and suggests a polynomially bound algorithm. This proposed algorithm has been implemented and tested on a variety of test problems and its performance is found to be quite satisfactory.     

A multi-stage stochastic supply network design problem with financial decisions and risk management

In this paper, a multi-period supply chain network design problem is addressed. Several aspects of practical relevance are considered such as those related with the financial decisions that must be accounted for by a company managing a supply chain. The decisions to be made comprise the location of the facilities, the flow of commodities and the investments to make in alternative activities to those directly related with the supply chain design. Uncertainty is assumed for demand and interest rates, which is described by a set of scenarios. Therefore, for the entire planning horizon, a tree of scenarios is built. A target is set for the return on investment and the risk of falling below it is measured and accounted for. The service level is also measured and included in the objective function. The problem is formulated as a multi-stage stochastic mixed-integer linear programming problem. The goal is to maximize the total financial benefit. An alternative formulation which is based upon the paths in the scenario tree is also proposed. A methodology for measuring the value of the stochastic solution in this problem is discussed. Computational tests using randomly generated data are presented showing that the stochastic approach is worth considering in these types of problems.     

The use of edge-directions and linear programming to enumerate vertices

Given a list of vectors that contains directions of the edges of a given polytope ℘ and the availability of an algorithm that solves linear programs over ℘, we describe a method for enumerating the vertices of ℘; in particular, the method is adaptable to polytopes which are presented as (linear) projections of polytopes having linear inequality representation. Polynomial complexity bounds under both the real and the binary computation models are derived when the dimension of the polytope is fixed and the given LP algorithm is polynomial. Dedicated to Professor Frank K. Hwang on the occasion of his sixty fifth birthday. Supported in part by a grant from ISF—the Israel Science Foundation, by a VPR grant at the Technion and by the Fund for the Promotion of Research at the Technion.     

The facility location problem with Bernoulli demands

This paper presents the facility location problem with Bernoulli demands. In this capacitated discrete location stochastic problem the goal is to define an a priori solution for the locations of the facilities and for the allocation of customers to the operating facilities that minimizes the sum of the fixed costs of the open facilities plus the expected value of the recourse function. The problem is formulated as a two-stage stochastic program and two different recourse actions are considered. For each of them, a closed form is presented for the recourse function and a deterministic equivalent formulation is obtained for the case in which the probability of demand is the same for all customers. Numerical results from computational experiments are presented and analyzed.     

A note on the facility location problem with stochastic demands

In this research note that the single source capacitated facility location problem with general stochastic identically distributed demands is studied. The demands considered are independent and identically distributed random variables with arbitrary distribution. The unified a priori solution for the locations of facilities and for the allocation of customers to the operating facilities is found. This solution minimizes the objective function which is the sum of the fixed costs and the value of one of two different recourse functions. For each case the recourse function is given in closed form and a deterministic equivalent formulation of the model is presented. Some numerical examples are also given.     

Pareto mimic algorithm: An approach to the team orienteering problem

The team orienteering problem is an important variant of the vehicle routing problem. In this paper, a new algorithm, called Pareto mimic algorithm, is proposed to deal with it. This algorithm maintains a population of incumbent solutions which are updated using Pareto dominance. It uses a new operator, called mimic operator, to generate a new solution by imitating an incumbent solution. Furthermore, to improve the quality of a solution, it employs an operator, called swallow operator which attempts to swallow (or insert) an infeasible node and then repair the resulting infeasible solution. A comparative study supports the effectiveness of the proposed algorithm, especially, our algorithm can quickly find new better results for several large-scale instances. We also demonstrate that Pareto mimic algorithm can be generalized to solve other routing problems, e.g., the capacitated vehicle routing problem.     

Target-guided algorithms for the container pre-marshalling problem

The container pre-marshalling problem (CPMP) aims to rearrange containers in a bay with the least movement effort; thus, in the final layout, containers are piled according to a predetermined order. Previous researchers, without exception, assumed that all the stacks in a bay are functionally identical. Such a classical problem setting is reexamined in this paper. Moreover, a new problem, the CPMP with a dummy stack (CPMPDS) is proposed. At terminals with transfer lanes, a bay includes a row of ordinary stacks and a dummy stack. The dummy stack is actually the bay space that is reserved for trucks. Therefore, containers can be shipped out from the bay. During the pre-marshalling process, the dummy stack temporarily stores containers as an ordinary stack. However, the dummy stack must be emptied at the end of pre-marshalling. In this paper, target-guided algorithms are proposed to handle both the classical CPMP and new CPMPDS. All the proposed algorithms guarantee termination. Experimental results in terms of the CPMP show that the proposed algorithms surpass the state-of-the-art algorithm.     

确定多属性群决策协调权的模型和方法

在权重信息不完全的多属性群决策过程中,当决策者给出了各自的关于方案的偏好序关系之后,需要检验是否存在一组能支持所有决策者意见的权重(即协调权).在定义偏好关系"重要度"的基础上,构造了一个{0,1}混合整数线性规划模型,该模型不仅能够判断协调权是否存在,而且可以识别出导致协调权不存在的"最不重要"的偏好序关系.此外还证明当决策者修改这些序关系后,群决策问题一定存在协调权.最后用一个例子说明了该模型的有效性和实用性.     

Efficient point coverage in wireless sensor networks

We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have ℓ types of sensors available with different sensing ranges and different costs. We want to find, given an integer σ ≥ 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least σ sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let k_i denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio . In applications where the distance of any two points has a fixed positive lower bound, each k_i is a constant, and so we have a polynomial-time approximation algorithms with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger. This research was supported in part by NSF under grant CCF-04080261 and by NSF of China under grant 60273062.     

An immune algorithm with stochastic aging and kullback entropy for the chromatic number problem

We present a new Immune Algorithm, IMMALG, that incorporates a Stochastic Aging operator and a simple local search procedure to improve the overall performances in tackling the chromatic number problem (CNP) instances. We characterize the algorithm and set its parameters in terms of Kullback Entropy. Experiments will show that the IA we propose is very competitive with the state-of-art evolutionary algorithms.     

Optimization models for the tool change scheduling problem

Traditional machine scheduling literature generally assumes that a machine is available at all times. Yet this assumption may not be accurate in real manufacturing systems. In many cases, a machine's tool must be changed after it has continuously worked for a period of time. This paper deals with a single machine scheduling problem subject to tool wear, given the allowed maximum continuous working time of the machine is _TL$T_{\mathrm{L}}$ (tool life) and the tool change time is _TC$T_{\mathrm{C}}$. Job processing and tool changes are scheduled simultaneously. In this paper, we examine this problem to minimize the total tardiness of jobs. Two mixed binary integer programming models are developed to optimally solve this problem. Computational experiments are performed to evaluate the models’ efficiency.     

Scenario aggregation in single-resource production planning models with uncertain demand

In this paper we present an application of the scenario aggregation approach proposed by Rockafellar and Wets to a simple standard multi-product multi-period production planning problem with uncertain demand and setup cost modelled by logical zero-one variables. The uncertainty in demand is expressed by a number of demand scenarios. As compared with more traditional approaches that require distributional assumptions and/or estimates of parameters from historical demand data, the scenario approach offers greater flexibility and makes it possible to take subjective information into account. The scenario aggregation principle and the corresponding progressive hedging algorithm offer a theoretically sound basis for generating consistent solutions for production planning models with uncertain demand. Since the production planning problem studied in this paper is of mixed-integer type the original scenario aggregation approach cannot be applied directly. However, since the integer variables in the production planning model are indirectly coupled to the continuous production decisions an alternative method in which only the production quantities are used to couple the different realizations can be used. This paper is a first attempt to perform this form of coupling. We illustrate the ideas on a small example and use this example to demonstrate how the solution can be evaluated in terms of flexibility measures.