带次模惩罚的优先设施选址问题的近似算法

研究带次模惩罚的优先设施选址问题, 每个顾客都有一定的服务水平要求, 开设的设施只有满足了顾客的服务水平要求, 才能为顾客提供服务, 没被服务的顾客对应一定的次模惩罚费用. 目标是使得开设费用、连接费用与次模惩罚费用之和最小. 给出该问题的整数规划、 线性规划松弛及其对偶规划. 基于原始对偶和贪婪增广技巧, 给出该问题的两个近似算法, 得到的近似比分别为3和2.375.     

Controlled perturbations for quadratically constrained quadratic programs

Consider a minimization problem of a convex quadratic function of several variables over a set of inequality constraints of the same type of function. The duel program is a maximization problem with a concave objective function and a set of constrains that are essentially linear. However, the objective function is not differentiable over the constraint region. In this paper, we study a general theory of dual perturbations and derive a fundamental relationship between a perturbed dual program and the original problem. Based on this relationship, we establish a perturbation theory to display that a well-controlled perturbation on the dual program can overcome the nondifferentiability issue and generate an ε-optimal dual solution for an arbitrarily small number ε. A simple linear program is then constructed to make an easy conversion from the dual solution to a corresponding ε-optimal primal solution. Moreover, a numerical example is included to illustrate the potential of this controlled perturbation scheme.     

Further Study on Augmented Lagrangian Duality Theory

In this paper, we present a necessary and sufficient condition for a zero duality gap between a primal optimization problem and its generalized augmented Lagrangian dual problems. The condition is mainly expressed in the form of the lower semicontinuity of a perturbation function at the origin. For a constrained optimization problem, a general equivalence is established for zero duality gap properties defined by a general nonlinear Lagrangian dual problem and a generalized augmented Lagrangian dual problem, respectively. For a constrained optimization problem with both equality and inequality constraints, we prove that first-order and second-order necessary optimality conditions of the augmented Lagrangian problems with a convex quadratic augmenting function converge to that of the original constrained program. For a mathematical program with only equality constraints, we show that the second-order necessary conditions of general augmented Lagrangian problems with a convex augmenting function converge to that of the original constrained program.This research is supported by the Research Grants Council of Hong Kong (PolyU B-Q359.)     

Risk aversion for an electricity retailer with second-order stochastic dominance constraints

In this paper we present the problem faced by an electricity retailer which searches to determine its forward contracting portfolio and the selling prices for its potential clients. This problem is formulated as a two-stage stochastic program including second-order stochastic dominance constraints. The stochastic dominance theory is used in order to reduce the risk suffering from low profits. The resulting deterministic equivalent problem is a mixed-integer linear program which is solved using commercial branch-and-cut software. Numerical results for a realistic case study are reported and relevant conclusions are drawn.     

随机容错设施布局问题的近似算法

在确定性的容错设施布局问题中, 给定顾客的集合和地址的集合. 在每个地址上可以开设任意数目的不同设施. 每个顾客j有连接需求r_j. 允许将顾客j连到同一地址的不同设施上. 目标是开设一些设施并将每个顾客j连到r_j个不同的设施上, 使得总开设费用和连接费用最小. 研究两阶段随机容错设施布局问题(SFTFP), 顾客的集合事先不知道, 但是具有有限多个场景并知道其概率分布. 每个场景指定需要服务的顾客的子集. 并且每个设施有两种类型的开设费用. 在第一阶段根据顾客的随机信息确定性地开设一些设施, 在第二阶段根据顾客的真实信息再增加开设一些设施．给出随机容错布局问题的线性整数规划和基于线性规划舍入的5-近似算法.     

带次模惩罚和随机需求的设施选址问题

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小. 根据该问题的特殊结构,给出原始对偶3-近似算法. 在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合. 最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.     

Recovering an optimal LP basis from an optimal dual solution

Given a linear program, we describe an approach for crossing over from an optimal dual solution to an optimal basic primal solution. It consists in restricting the dual problem to a small box around the available optimal dual solution then, resolving the associated modified primal problem.     

Nonlinear Lagrange Duality Theorems and Penalty Function Methods In Continuous Optimization

We propose a general dual program for a constrained optimization problem via generalized nonlinear Lagrangian functions. Our dual program includes a class of general dual programs with explicit structures as special cases. Duality theorems with the zero duality gap are proved under very general assumptions and several important corollaries which include some known results are given. Using dual functions as penalty functions, we also establish that a sequence of approximate optimal solutions of the penalty function converges to the optimal solution of the original optimization problem.     

Robust Duality for Fractional Programming Problems with Constraint-Wise Data Uncertainty

In this paper, we examine duality for fractional programming problems in the face of data uncertainty within the framework of robust optimization. We establish strong duality between the robust counterpart of an uncertain convex–concave fractional program and the optimistic counterpart of its conventional Wolfe dual program with uncertain parameters. For linear fractional programming problems with constraint-wise interval uncertainty, we show that the dual of the robust counterpart is the optimistic counterpart in the sense that they are equivalent. Our results show that a worst-case solution of an uncertain fractional program (i.e., a solution of its robust counterpart) can be obtained by solving a single deterministic dual program. In the case of a linear fractional programming problem with interval uncertainty, such solutions can be found by solving a simple linear program.     

Strictly feasible solutions and strict complementarity in multiple objective linear optimization

Recently, Luc defined a dual program for a multiple objective linear program. The dual problem is also a multiple objective linear problem and the weak duality and strong duality theorems for these primal and dual problems have been established. Here, we use these results to prove some relationships between multiple objective linear primal and dual problems. We extend the available results on single objective linear primal and dual problems to multiple objective linear primal and dual problems. Complementary slackness conditions for efficient solutions, and conditions for the existence of weakly efficient solution sets and existence of strictly primal and dual feasible points are established. We show that primal-dual (weakly) efficient solutions satisfying strictly complementary conditions exist. Furthermore, we consider Isermann’s and Kolumban’s dual problems and establish conditions for the existence of strictly primal and dual feasible points. We show the existence of primal-dual feasible points satisfying strictly complementary conditions for Isermann’s dual problem. Also, we give an alternative proof to establish necessary conditions for weakly efficient solutions of multiple objective programs, assuming the Kuhn–Tucker (KT) constraint qualification. We also provide a new condition to ensure the KT constraint qualification.     

A projection method for the uncapacitated facility location problem

Several algorithms already exist for solving the uncapacitated facility location problem. The most efficient are based upon the solution of the strong linear programming relaxation. The dual of this relaxation has a condensed form which consists of minimizing a certain piecewise linear convex function. This paper presents a new method for solving the uncapacitated facility location problem based upon the exact solution of the condensed dual via orthogonal projections. The amount of work per iteration is of the same order as that of a simplex iteration for a linear program inm variables and constraints, wherem is the number of clients. For comparison, the underlying linear programming dual hasmn + m + n variables andmn +n constraints, wheren is the number of potential locations for the facilities. The method is flexible as it can handle side constraints. In particular, when there is a duality gap, the linear programming formulation can be strengthened by adding cuts. Numerical results for some classical test problems are included.     

Stochastic capacity expansion with multiple sources of capacity

In this paper, we consider the multi-period single resource stochastic capacity expansion problem with three sources of capacity: permanent, contract, and spot market. The problem is modeled as a multi-stage stochastic integer program. We show that the problem has the totally unimodular property and develop polynomial-time primal and dual algorithms to solve the problem.     

非线性二层规划问题的全局优化方法

对于下层为线性规划问题的一类非线性二层规划问题,利用线性规划的对偶理论,将其转化为一个单层优化问题,同时取下层问题的对偶间隙作为惩罚项,构造了一个相应的罚问题,然后提出了一个求解该类二层规划问题的全局优化方法。最后,数值结果表明,所提出的方法是可行的。     

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.     

A Practical Algorithm for Computing a Subadditive Dual Function for Set Partitioning

Recently, a new algorithm for computing an optimal subadditive dual function to an integer program has been proposed. In this paper we show how to apply the algorithm to the set partitioning problem. We give several enhancements to the algorithm and we report computational experiments. The results show that it is tractable to obtain an optimal subadditive function for small and medium size problems. To the best of our knowledge this is the first work that reports computational experiments on computing an optimal subadditive dual function.     

The minimal cone for conic linear programming

It is known that the minimal cone for the constraint system of a conic linear programming problem is a key component in obtaining strong duality without any constraint qualification. For problems in either primal or dual form, the minimal cone can be written down explicitly in terms of the problem data. However, due to possible lack of closure, explicit expressions for the dual cone of the minimal cone cannot be obtained in general. In the particular case of semidefinite programming, an explicit expression for the dual cone of the minimal cone allows for a dual program of polynomial size that satisfies strong duality. In this paper we develop a recursive procedure to obtain the minimal cone and its dual cone. In particular, for conic problems with so-called nice cones, we obtain explicit expressions for the cones involved in the dual recursive procedure. As an example of this approach, the well-known duals that satisfy strong duality for semidefinite programming problems are obtained. The relation between this approach and a facial reduction algorithm is also discussed.     

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rⁿ is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Posynomial geometric programming as a special case of semi-infinite linear programming

This paper develops a wholly linear formulation of the posynomial geometric programming problem. It is shown that the primal geometric programming problem is equivalent to a semi-infinite linear program, and the dual problem is equivalent to a generalized linear program. Furthermore, the duality results that are available for the traditionally defined primal-dual pair are readily obtained from the duality theory for semi-infinite linear programs. It is also shown that two efficient algorithms (one primal based and the other dual based) for geometric programming actually operate on the semi-infinite linear program and its dual.     

Duality inequalities as a numerical aid

This note re-examines the problem of estimating the minimum value of a convex program. To obtain a lower bound to this value a dual program is formulated. The dual involves only explicitly given functions and only inequality constraints. No nonlinear equality constraints appear. Thus a numerically feasible algorithm is obtained.     

Unconstrained convex programming approach to linear programming

Recently, Fang proposed approximating a linear program in the Karmarkar standard form by adding an entropic barrier function to the objective function and derived an unconstrained dual concave program. We present in this note a necessary and sufficient condition for the existence of a dual optimal solution to the perturbed problem. In addition, a sharp upper bound of error estimation in this approximation scheme is provided.