A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

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.     

A linear programming approach to solving bilinear programmes

This paper discusses the maximization of a bilinear function over two independent polytopes. The maximization problem is converted into a max—min problem, using duality. This problem is then solved via a sequence of dual linear programmes, whose constraint vectors are successively determined bytth order optima of a master linear programme.     

极大限制边连通超图的两个充分条件

图的限制边连通度是经典边连通度的推广,可用于精确度量网络的容错性.极大限制边连通图是使限制边连通度达到最优的一类图.首先将图的限制边连通度和最小边度的概念推广到r一致线性超图H,证明当H的最小度δ(H)≥r+1时,H的最小边度ξ(H)是它的限制边连通度λ′(H)的一个上界,并将满足ξ(H)=λ′(H)的H称为极大限制边连通超图,然后证明n个顶点的r一致线性超图H如果满足δ(H)≥(n-1)/(2(r-1))+(r-1),则它是极大限制边连通的,最后证明直径为2,围长至少为4的一致线性超图是极大限制边连通的.所得结论是图中相关结果的推广.     

线性规划问题罚函数方法的一种统一形式

用一种统一的方式,讨论了线性规划问题中常用的罚函数方法及其对偶性.并将这种方法应用到等式约束二次规划问题中.     

Duality in Fuzzy Linear Programming: Some New Concepts and Results

A class of fuzzy linear programming (FLP) problems based on fuzzy relations is introduced, the concepts of feasible and -efficient solutions are defined. The class of crisp (classical) LP problems and interval LP problems can be embedded into the class of FLP ones. Moreover, for FLP problems a new concept of duality is introduced and the weak and strong duality theorems are derived. The previous results are applied to the special case of interval LP and compared to the existing literature.     

A Dual Parametrization Method for Convex Semi-Infinite Programming

We formulate convex semi-infinite programming problems in a functional analytic setting and derive optimality conditions and several duality results, based on which we develop a computational framework for solving convex semi-infinite programs.     

Duality in mathematics and linear and integer programming

Linear programming (LP) duality is examined in the context of other dualities in mathematics. The mathematical and economic properties of LP duality are discussed and its uses are considered. These mathematical and economic properties are then examined in relation to possible integer programming (IP) dualities. A number of possible IP duals are considered in this light and shown to capture some but not all desirable properties. It is shown that inherent in IP models are inequality and congruence constraints, both of which give on their own well-defined duals. However, taken together, no totally satisfactory dual emerges. The superadditive dual based on the Gomory and Chvátal functions is then described, and its properties are contrasted with LP duals and other IP duals. Finally, possible practical uses of IP duals are considered.The author is indebted to Professor H. B. Griffiths for many stimulating conversations on this topic.     

Stability of the primal-dual partition in linear semi-infinite programming

We analyse the primal-dual states in linear semi-infinite programming (LSIP), where we consider the primal problem and the so called Haar's dual problem. Any linear programming problem and its dual can be classified as bounded, unbounded or inconsistent, giving rise to nine possible primal-dual states, which are reduced to six by the weak duality property. Recently, Goberna and Todorov have studied this partition and its stability in continuous LSIP in a series of papers [M.A. Goberna and M.I. Todorov, Primal, dual and primal-dual partitions in continuous linear semi-infinite programming, Optimization 56 (2007), pp. 617–628; M.A. Goberna and M.I. Todorov, Generic primal-dual solvability in continuous linear semi-infinite programming, Optimization 57 (2008), pp. 239–248]. In this article we consider the general case, with no continuity assumptions, discussing the maintenance of the primal-dual state of the problem by allowing small perturbations of the data. We characterize the stability of all of the six possible primal-dual states through necessary and sufficient conditions which depend on the data, and can be easily checked, showing some differences with the continuous case. These conditions involve the strong Slater constraint qualification, and some distinguished convex sets associated to the data.     

On fuzzy linear programming

Fuzzy multi-objective and fuzzy Goal Programming are discussed in connection with several membership functions which are used to transform the original problem into three equivalent linear programming problems. Existence and uniqueness theorems are given. Fuzzy duality is presented, and an extension of the initial fuzzy problem arises immediately from it.     

Duality via halfspaces

This note shows that half spaces play a very special role in the development of duality. In addition to the minimum norm duality, the duality in linear programming, and Wolfe's and Johri's formulations in nonlinear programming can all be derived via half spaces by following an identical five step procedure.     

Graphical analysis of duality and the Kuhn-Tucker conditions in linear programming

Careful inspection of the geometry of the primal linear programming problem reveals the Kuhn-Tucker conditions as well as the dual. Many of the well-known special cases in duality are also seen from the geometry, as well as the complementary slackness conditions and shadow prices. The latter at demonstrated to differ from the dual variables in situations involving primal degeneracy. Virtually all the special relationships between linear programming and duality theory can be seen from the geometry of the primal and an elementary application of vector analysis.     

A note about linear inequality systems and duality

The optimization of a linear function on a closed convex set,F, can be stated as a linear semi-infinite program, sinceF is the solution set of (usually) infinite linear inequality systems, the so-called linear representations ofF. The duality properties of these programs are analyzed when the linear representation ofF ranges in some well known classes of linear inequality systems. This paper provides propositions on the duality diagrams of Farkas-Minkowski, canonically closed, compact and closed systems. Converse statements are also given.

---

Zusammenfassung Die Optimierung einer linearen Funktion auf einer konvexen abgeschlossenen MengeF kann als semi-infinites lineares Programm aufgefaßt werden, daF als Durchschnitt (unendlich) vieler Halbräume dargestellt werden kann. Es werden Dualitätseigenschaften dieser Programme untersucht, wobei von verschiedenen linearen Darstellungen fürF ausgegangen wird. Die Arbeit enthält Sätze über Dualitätsbeziehungen von Farkas-Minkowski, kanonisch abgeschlossene, kompakte und abgeschlossene Systeme. Es werden auch umgekehrte Beziehungen angegeben.

     

简单网络流对策的相对N-核

主要研究简单网络流对策中相对N-核的算法.当网络中最大流值等于1时,证明相对N-核与对策的核心相同,不一定是单点集;而当网络中最大流值大于1时,利用Kopelowitz's序列线性规划方法和线性规划对偶理论,证明相对N-核与N-核相同(同为单点集),并且可在局中人个数的多项式时间内得到求解.     

Approximate Solutions and Duality Theorems for Continuous-Time Linear Fractional Programming Problems

This article proposes a practical computational procedure to solve a class of continuous-time linear fractional programming problems by designing a discretized problem. Using the optimal solutions of proposed discretized problems, we construct a sequence of feasible solutions of continuous-time linear fractional programming problem and show that there exists a subsequence that converges weakly to a desired optimal solution. We also establish an estimate of the error bound. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.     

Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date

We consider a batch scheduling problem on a single machine which processes jobs with resource dependent setup and processing time in the presence of fuzzy due-dates given as follows:1. There are n independent non-preemptive and simultaneously available jobs processed on a single machine in batches. Each job j has a processing time and a due-date.2. All jobs in a batch are completed together upon the completion of the last job in the batch. The batch processing time is equal to the sum of the processing times of its jobs. A common machine setup time is required before the processing of each batch.3. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource.4. The due-date of each job is flexible. That is, a membership function describing non-decreasing satisfaction degree about completion time of each job is defined.5. Under above setting, we find an optimal batch sequence and resource values such that the total weighted resource consumption is minimized subject to meeting the job due-dates, and minimal satisfaction degree about each due-date of each job is maximized. But usually we cannot optimize two objectives at a time. So we seek non-dominated pairs i.e. the batch sequence and resource value, after defining dominance between solutions.A polynomial algorithm is constructed based on linear programming formulations of the corresponding problems.     

The gap function of a convex program

The gap function expresses the duality gap of a convex program as a function of the primal variables only. Differentiability and convexity properties are derived, and a convergent minimization algorithm is given. An example gives a simple one-variable interpretation of weak and strong duality. Application to user-equilibrium traffic assignment yields an appealing alternative optimization problem.