Duality-based regularization in a linear convex mathematical programming problem

For a linear convex mathematical programming (MP) problem with equality and inequality constraints in a Hilbert space, a dual-type algorithm is constructed that is stable with respect to input data errors. In the algorithm, the dual of the original optimization problem is solved directly on the basis of Tikhonov regularization. It is shown that the necessary optimality conditions in the original MP problem are derived in a natural manner by using dual regularization in conjunction with the constructive generation of a minimizing sequence. An iterative regularization of the dual algorithm is considered. A stopping rule for the iteration process is presented in the case of a finite fixed error in the input data.     

Necessary conditions for an extremum in a mathematical programming problem

For minimization problems with equality and inequality constraints, first-and second-order necessary conditions for a local extremum are presented. These conditions apply when the constraints do not satisfy the traditional regularity assumptions. The approach is based on the concept of 2-regularity; it unites and generalizes the authors’ previous studies based on this concept.     

A mathematical programming problem with singular mixed pointwise-integral constraints

We investigate an infinite dimensional optimization problem which constraints are singular integral-pointwise ones. We give some partial results of existence for a solution in some particular cases. However, the lack of compactness, even in L¹ prevents to conclude in the general case. We give an existence result for a weak solution (as a measure) that we are able to describe. The regularity of such a solution is still an open problem.     

General mathematical programming formulations for the statistical classification problem

The study presents mathematical programming formulations for the statistical classification problem. The formulations maximize the number of observations that are properly categorized. The models are easily modified for any number of categories of classification. The formulation were tested on a standard problem.     

Regularity and stability for the mathematical programming problem in Banach spaces

This paper deals with a regularity assumption for the mathematical programming problem in Banach spaces. The attractive feature of our constraint qualification is the fact that it can be considered as a condition on the active part only of the constraint, and that it is preserved under small perturbations. Moreover, we show that our condition is almost equivalent to the existence of a non-empty and weakly compact set of Lagrange multipliers. The main step in the proof of our results is a generalization of the open mapping theorem.The early parts of this article result from fruitful correspondence with S. Kurcyusz, who died tragically in 1978. This paper is dedicated to his memory.     

A mathematical programming model for the bus deviation route problem

In small towns, or in those peripherical metropolitan areas in which the demand for public transportation is relatively low, the objectives of the bus route planner are different from those faced in highly congested networks. Some towns, also in Italy, are experimenting with urban public transportation systems where regular bus routes are designed which allow users located at specific points outside the main line to signal their presence to the bus driver, who then deviates from the main route to satisfy this demand. This way the bus line is a mixture between a regular line and a dial-a-ride system. The bus deviation route problem is concerned with the design problem which arises in planning the location of the demand points outside the line. A model is presented which takes into account both the advantage of passengers served by this deviation device and the disadvantage suffered by passengers on the bus, whose travel time increases during deviations, and by passengers downstream of the deviation whose waiting time also increases. Through some modeling assumption we are able to represent this problem as a mixed integer linear programming problem, whose relatively low dimension allows for exact solution through standard simplex-based branch and bound code. The proposed model has been applied to a real case and some results of this are presented and discussed.     

A mathematical programming viewpoint for solving the ultimate pit problem

In 1965 Helmut Lerchs and Ingo Grossmann presented to the mining community an algorithm to find the optimum design for an open pit mine. In their words, “the objective is to design the contour of a pit so as to maximize the difference between total mine value of the ore extracted and the total extraction cost of ore and waste”. They modeled the problem in graph theoretic terms and showed that an optimal solution of the ultimate pit problem is equivalent to finding the maximum closure of their graph based model. In this paper, we develop a network flow algorithm based on the dual to solve the same problem. We show how this algorithm is closely related to Lerchs and Grossmann's and how the steps in their algorithm can be viewed in mathematical programming terms. This analysis adds insight to the algorithm of Lerchs and Grossmann and shows where it can be made more efficient. As in the case Lerchs and Grossmann, our algorithm allows us to use very efficient data structures based on graphs that represent the data and constraints.. 1782 1528 V 3     

A system of inequalities and nondifferentiable mathematical programming

A system of inequalities involving nondifferentiable functions, originally introduced by Eisenberg, is extended. This result is then applied to establish optimality criteria and a dual theorem for a nondifferentiable mathematical program involving quasiconvexity in its equality constraints and inequality constraints. These are natural extensions of results recently established by Mond.The author is grateful to Dr. D. J. Fleming, St. Lawrence University, for helpful discussion.     

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.     

Environmental supply chain network design using multi-objective fuzzy mathematical programming

The concern about environmental impact of business activities has spurred an interest in designing environmentally conscious supply chains. This paper proposes a multi-objective fuzzy mathematical programming model for designing an environmental supply chain under inherent uncertainty of input data in such problem. The proposed model is able to consider the minimization of multiple environmental impacts beside the traditional cost minimization objective to make a fair balance between them. A life cycle assessment-based (LCA-based) method is applied to assess and quantify the environmental impact of different options for supply chain network configuration. Also, to solve the proposed multi-objective fuzzy optimization model, an interactive fuzzy solution approach is developed. A real industrial case is used to demonstrate the significance and applicability of the developed fuzzy optimization model as well as the usefulness of the proposed solution approach.     

A multi-phase mathematical programming approach for effective supply chain design

A supply chain is an alliance of independent business processes, such as supplier, manufacturing, and distribution processes that perform the critical functions in the order fulfillment process. Effective design and management of supply chains assists in production and delivery of a variety of products at low cost, high quality, and short lead times. Although the importance of supply chain design is emphasized in the literature, few formal decision models have been proposed for this purpose. This paper presents a multi-phase mathematical programming approach for effective supply chain design. More specifically, the methodology develops and applies a combination of multi-criteria efficiency models, based on game theory concepts, and linear and integer programming methods. Model application and insights are detailed through numerical illustrations.     

Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

Constraint classification in mathematical programming

Consider a set of algebraic inequality constraints defining either an empty or a nonempty feasible region. It is known that each constraint can be classified as either absolutely strongly redundant, relatively strongly redundant, absolutely weakly redundant, relatively weakly redundant, or necessary. We show that is is worth making a distinction between weakly necessary constraints and strongly necessary constraints. We also present afeasible set cover method which can detect both weakly and strongly necessary constraints.The main interest in constraint classification is due to the advantages gained by the removal of redundant constraints. Since classification errors are likely to occur, we examine how the removal of a single constraint can affect the classification of the remaining constraints.     

Hybrid computation in mathematical programming

It is shown that hybrid computation facilitates the solving of problems in the field of mathematical programming. First, the most important features of hybrid computation are discussed. The main part of the paper deals with examples of computational methods in which hybrid computation can be applied succesfully. The main concentration is on constrained static parameter optimization, where for brevity only penalty function techniques are considered. The use of a penalty function having an extra parameter is discussed rather extensively.     

Decomposition in general mathematical programming

In this paper a unifying framework is presented for the generalization of the decomposition methods originally developed by Benders (1962) and Dantzig and Wolfe (1960). These generalizations, calledVariable Decomposition andConstraint Decomposition respectively, are based on the general duality theory developed by Tind and Wolsey. The framework presented is of a general nature since there are no restrictive conditions imposed on problem structure; moreover, inaccuracies and duality gaps that are encountered during computations are accounted for. The two decomposition methods are proven not to cycle if certain (fairly general) conditions are met. Furthermore, finite convergence can be ensured under the traditional finiteness conditions and asymptotic convergence can be guaranteed once certain continuity conditions are met. The obvious symmetry between both types of decomposition methods is explained by establishing a duality relation between the two, which extends a similar result in Linear Programming. A remaining asymmetry in the asymptotic convergence results is argued to be a direct consequence of a fundamental asymmetry that resides in the Tind-Wolsey duality theory. It can be shown that in case the latter asymmetry disappears, the former does too. Other decomposition techniques, such as Lagrangean Decomposition and Cross Decomposition, turn out to be captured by the general framework presented here as well.This study was supported by the Netherlands Foundation for Mathematics (SMC) with financial aid from the Netherlands Organization for Scientific Research (NWO).Part of this work was done while on leave at the Wharton School of the University of Pennsylvania.     

Error bounds in mathematical programming

Originated from the practical implementation and numerical considerations of iterative methods for solving mathematical programs, the study of error bounds has grown and proliferated in many interesting areas within mathematical programming. This paper gives a comprehensive, state-of-the-art survey of the extensive theory and rich applications of error bounds for inequality and optimization systems and solution sets of equilibrium problems. This work is based on research supported by the U.S. National Science Foundation under grant CCR-9624018.     

Potential-reduction methods in mathematical programming

We provide a survey of interior-point methods for linear programming and its extensions that are based on reducing a suitable potential function at each iteration. We give a fairly complete overview of potential-reduction methods for linear programming, focusing on the possibility of taking long steps and the properties of the barrier function that are necessary for the analysis. We then describe briefly how the methods and results can be extended to certain convex programming problems, following the approach of Nesterov and Todd. We conclude with some open problems. Research supported in part by NSF, AFOSR and ONR through NSF Grant DMS-8920550. Some of this work was done while the author was on a sabbatical leave from Cornell University visiting the Department of Mathematics at the University of Washington.     

On the solution of large engineering design problems via mathematical programming

The method of moving asymptotes (MMA) is known to work well for the solution of mathematical programs arising in engineering design problems. Recently, the method has been extended by using two interior point approaches for the solution of the arising convex subproblems. Besides function and gradient evaluations, i.e. finite element analyses, the main computational work has to be done in the solution of a large sequence of linear systems. The interior point approach provides more flexibility in the formulation of these systems which is advantageous for large scale applications.     

The design centering problem as a D.C. programming problem

The following problem is studied: Given a compact setS inR ⁿ and a Minkowski functionalp(x), find the largest positive numberr for which there existsx S such that the set of ally R ⁿ satisfyingp(y–x) r is contained inS. It is shown that whenS is the intersection of a closed convex set and several complementary convex sets (sets whose complements are open convex) this design centering problem can be reformulated as the minimization of some d.c. function (difference of two convex functions) overR ⁿ . In the case where, moreover,p(x) = (x ^T Ax)^1/2, withA being a symmetric positive definite matrix, a solution method is developed which is based on the reduction of the problem to the global minimization of a concave function over a compact convex set.