Interactive fuzzy programming for multi-level 0–1 programming problems through genetic algorithms

In this paper, we propose interactive fuzzy programming for multi-level 0–1 programming problems through genetic algorithms. Our method is supposed to apply to hierarchical decision problems in which decision-making at each level is sequential from upper to lower level and decision makers are essentially cooperative. After determining the fuzzy goals of the decision makers at all levels, a satisfactory solution is derived efficiently by updating the satisfactory degrees of the decision makers at the upper level with considerations of overall satisfactory balance among all levels. An illustrative numerical example for three-level 0–1 programming problems is provided to demonstrate the feasibility of the proposed method.     

Computer programs for non‐linear programming

In this paper we consider the problem of maximizing a non‐linear or linear objective function subject to non‐linear and/or linear constraints. The approach used is an adaptive random search with some non‐random searches built‐in. The algorithm begins with a given point which is replaced by another point if the latter satisfies each of the constraints and results in a bigger functional value. The process of moving from one point to a better point is repeated many times. The value of each of the coordinates of the next point is determined by one of several ways; for example, a coordinate is sometimes forced to have the same value as the value of the corresponding coordinate of the current feasible point. In this algorithm, a candidate point receives no further computational considerations as soon as it is found to be unfeasible; this makes the algorithm general. Computer programs illustrating the details of the new algorithm are given and computational results of two numerical test problems from the literature are presented. Optimality was reached in each of these two problems.     

Zero—one programming with multiple criteria

The study of multiple criteria problems is not new, but during the last seventeen years more and more study has been done in this area. The study of 0–1 multiple criteria problems started much later than the study of continuous multiple criteria problems. Some of the earliest works on 0–1 problems with multiple criteria was first presented in 1973. Quite a few solution methods have been developed since then, especially during the last seven years. In this paper most of these methods and some applications will be treated.     

Fuzzy goal programming — An additive model

An additive model to solve Fuzzy Goal Programming (FGP) is formulated. The method uses arithmetic addition to aggregate the fuzzy goals to construct the relevant decision function. Cardinal and ordinal weights for nonequivalent fuzzy goals are also incorporated in the method. The solution procedure is illustrated with a numerical example.     

Piecewise w∞-equitable efficiency in multiobjective programming

Acta Mathematicae Applicatae Sinica, English Series - In equitable multiobjective optimization all the objectives are uniformly optimized, but in some cases the decision maker believes that some of...     

ɛ-duality theorem of nondifferentiable nonconvex multiobjective programming

Necessary Kuhn-Tucker conditions up to precision without constraint qualification for -Pareto optimality of multiobjective programming are derived. This article suggests the establishment of a Wolfe-type -duality theorem for nondifferentiable, nonconvex, multiobjective minimization problems. The -vector Lagrangian and the generalized -saddle point for Pareto optimality are studied.     

Nonsmooth minimax fractional programming involving η-pseudolinear functions

This article deals with the necessary and sufficient optimality conditions for a class of nonsmooth minimax fractional programming problems with locally Lipschitz η-pseudolinear functions. Utilizing these optimality criteria, we formulate two types of dual models and establish weak and strong duality results. The results of this article extend several known results from the literature to a wider class of optimization problems.     

ɛ-Duality theorem of nondifferentiable nonconvex multiobjective programming

This technical reply deals with the relations between Ref. 1 and Refs. 2–4.     

A “build-down” scheme for linear programming

We propose a build-down scheme for Karmarkar's algorithm and the simplex method for linear programming. The scheme starts with an optimal basis candidate set including all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated from. As these methods iterate, is eventually built-down to a set that contains only the optimal basic columns.     

Chvátal closures for mixed integer programming problems

Chvátal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedronP and integral vectorw, if max(wx|x P, wx integer} =t, thenwx t is valid for all integral vectors inP. We consider the variant of this step where the requirement thatwx be integer may be replaced by the requirement that be integer for some other integral vector . The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedronP, the set of vectors that satisfy every cutting plane forP with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvátal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.Supported by Sonderforschungsbereich 303 (DFG) and by NSF Grant Number ECS-8611841.Supported by NSF Grant Number ECS-8418392 and Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, FR Germany.     

A predictor-corrector smoothing method for second-order cone programming

In this paper, the second order cone programming problem is studied. By introducing a parameter into the Fischer-Burmeister function, a predictor-corrector smoothing Newton method for solving the problem is presented. The proposed algorithm does neither have restrictions on its starting point nor need additional computation which keep the iteration sequence staying in the given neighborhood. Furthermore, the global and the local quadratic convergence of the algorithm are obtained, among others, the local quadratic convergence of the algorithm is established without strict complementarity. Preliminary numerical results indicate that the algorithm is effective.     

A quadratic programming approach to the Randić index

Let G(k, n) be the set of connected graphs without multiple edges or loops which have n vertices and the minimum degree of vertices is k. The Randi? index χ = χ(G) of a graph G   is defined by χ(G)=_∑(uv)(_δuδv)^-1/2$\chi (G)={\sum }_{(\mathit{uv})}({\delta }_u{\delta }_v{)}^{-1/2}$, where δ_u is the degree of vertex u and the summation extends over all edges (uv) of G. Caporossi et al. [G. Caporossi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs IV: Chemical trees with extremal connectivity index, Computers and Chemistry 23 (1999) 469–477] proposed the use of linear programming as one of the tools for finding the extremal graphs. In this paper we introduce a new approach based on quadratic programming for finding the extremal graphs in G(k, n) for this index. We found the extremal graphs or gave good bounds for this index when the number n_k of vertices of degree k is between n − k and n. We also tried to find the graphs for which the Randi? index attained its minimum value with given k (k ? n/2) and n. We have solved this problem partially, that is, we have showed that the extremal graphs must have the number n_k of vertices of degree k less or equal n − k and the number of vertices of degree n − 1 less or equal k.     

An evolutionary heuristic for quadratic 0–1 programming

In this paper we present a heuristic algorithm for the well-known Unconstrained Quadratic 0–1 Programming Problem. The approach is based on combining solutions in a genetic paradigm and incorporates intensification algorithms used to improve solutions and speed up the method. Extensive computational experiments on instances with up to 500 variables are presented and we compare our approach both with powerful heuristic and exact algorithms from the literature establishing the effectiveness of the method in terms of solutions quality and computing time.     

Stochastic goal programming: A mean–variance approach

We propose a stochastic goal programming (GP) model leading to a structure of mean–variance minimisation. The solution to the stochastic problem is obtained from a linkage between the standard expected utility theory and a strictly linear, weighted GP model under uncertainty. The approach essentially consists in specifying the expected utility equation corresponding to every goal. Arrow's absolute risk aversion coefficients play their role in the calculation process. Once the model is defined and justified, an illustrative example is developed.     

Perfect duality in semi–infinite and semidefinite programming

This paper develops new relationships between the recently constructed semidefinite programming perfect duality and the earlier perfect duality achieved for linear semi–infinite programming. Applying the linear semi–infinite perfect duality construction to semidefinite programming yields a larger feasible set than the one obtained by the newly constructed semidefinite programming regularized perfect dual. Received: November 10, 1997 / Accepted: March 5, 1999?Published online May 3, 2001     

General purpose heuristics for integer programming—Part I

In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a class by class basis, but which apply to a broader range of problems, have significant value. We show that certain ideas proposed in the 1970s, which are often overlooked, can be reformulated and linked with more recent developments to give a useful theoretical framework for generating general purpose IP heuristics. This framework, which has the appeal of being highly visual, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.     

A smoothing projected Newton-type algorithm for semi-infinite programming

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

Fractional 0–1 programming: applications and algorithms

We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.     

Large-scale 0–1 linear programming on distributed workstations

We present a methodology which uses a collection of workstations connected by an Ethernet network as a parallel processor for solving large-scale linear programming problems. On the largest problems we tested, linear and super-linear speedups have been achieved. Using the branch-and-cut approach of Hoffman, Padberg and Rinaldi, eight workstations connected in parallel solve problems from the test set documented in the Crowder, Johnson and Padberg 1983Operations Research article. Very inexpensive, networked workstations are now solving in minutes problems which were once considered not solvable in economically feasible times. In this peer-to-peer (as opposed to master-worker) implementation, interprocess communication was accomplished by using shared files and resource locks. Effective communication between processes was accomplished with a minimum of overhead (never more than 8% of total processing time). The implementation procedures and computational results will be presented.Supported in part by a grant from the Digital Equipment Corporation.Supported in part by grants from the Office of Naval Research and the National Science Foundation (ECS-8615438).     

Nonsmooth multiobjective programming: strong Kuhn–Tucker conditions

We consider a multiobjective optimization problem with a feasible set defined by inequality and equality constraints and a set constraint, where the objective and constraint functions are locally Lipschitz. Several constraint qualifications are given in such a way that they generalize the classical ones, when the functions are differentiable. The relationships between them are analyzed. Then, we establish strong Kuhn–Tucker necessary optimality conditions in terms of the Clarke subdifferentials such that the multipliers of the objective function are all positive. Furthermore, sufficient optimality conditions under generalized convexity assumptions are derived. Moreover, the concept of efficiency is used to formulate duality for nonsmooth multiobjective problems. Wolf and Mond–Weir type dual problems are formulated. We also establish the weak and strong duality theorems.