Integrated use of fuzzy c-means and convex programming for capacitated multi-facility location problem

In this study a fuzzy c-means clustering algorithm based method is proposed for solving a capacitated multi-facility location problem of known demand points which are served from capacitated supply centres. It involves the integrated use of fuzzy c-means and convex programming. In fuzzy c-means, data points are allowed to belong to several clusters with different degrees of membership. This feature is used here to split demands between supply centers. The cluster number is determined by an incremental method that starts with two and designated when capacity of each cluster is sufficient for its demand. Finally, each group of cluster and each model are solved as a single facility location problem. Then each single facility location problem given by fuzzy c-means is solved by convex programming which optimizes transportation cost is used to fine-tune the facility location. Proposed method is applied to several facility location problems from OR library (Osman & Christofides, 1994) and compared with centre of gravity and particle swarm optimization based algorithms. Numerical results of an asphalt producer’s real-world data in Turkey are reported. Numerical results show that the proposed approach performs better than using original fuzzy c-means, integrated use of fuzzy c-means and center of gravity methods in terms of transportation costs.     

A Long-step barrier method for convex quadratic programming

In this paper we propose a long-step logarithmic barrier function method for convex quadratic programming with linear equality constraints. After a reduction of the barrier parameter, a series of long steps along projected Newton directions are taken until the iterate is in the vicinity of the center associated with the current value of the barrier parameter. We prove that the total number of iterations isO(nL) orO(nL), depending on how the barrier parameter is updated.On leave from Eötvös University, Budapest and partially supported by OTKA 2116.     

Dynamic programming and convex clustering

In this paper the notion of convexity of clusterings for the given ordering of units is introduced. In the case when at least one (optimal) solution of the clustering problem is convex, dynamic programming leads to a polynomial algorithm with complexityO(kn ³). We prove that, for several criterion functions, convex optimal clusterings exist when dissimilarity is pyramidal for a given ordering of units.This research was supported in part by the Research Council of Slovenia.     

等式约束凸二次规划解析的新型神经网络方法*

针对不同于传统基于梯度法的递归神经网络定义一种基于标量范数取值的非负能量函数,通过定义一种基于向量取值的不定无界的误差函数,构建了一种能实时求解具有线性等式约束的凸二次规划问题。基于Simulink仿真平台的计算机实验结果表明,该新型神经网络模型能够准确有效地求解此类二次规划问题。     

Dynamic programming for free-time problems with endpoint constraints

If we are able to find a local verification function associated with an admissible trajectory x(^.), then x(^.) is a local minimizer. It is of interest therefore to know when such local verification functions exist. In this paper it is shown that the existence of a local verification function is necessary for x(^.) to be a local minimizer, under a normality hypothesis. The novelty of these results is that they treat problems with a general endpoint constraint and where the endtime is a choice variable. Here the value function of the original problem does not serve as a local verification function; instead it must be constructed from some derived problem. The data are allowed to be measurable in the time variable, and the normality hypothesis is expressed in terms of recent free-endtime necessary conditions of optimality for problems with measurable time dependence.     

An application of a merit function for solving convex programming problems

This paper presents a gradient neural network model for solving convex nonlinear programming (CNP) problems. The main idea is to convert the CNP problem into an equivalent unconstrained minimization problem with objective energy function. A gradient model is then defined directly using the derivatives of the energy function. It is also shown that the proposed neural network is stable in the sense of Lyapunov and can converge to an exact optimal solution of the original problem. It is also found that a larger scaling factor leads to a better convergence rate of the trajectory. The validity and transient behavior of the neural network are demonstrated by using various examples.     

A new neural network for solving nonlinear convex programs with linear constraints

In this paper, a new neural network was presented for solving nonlinear convex programs with linear constrains. Under the condition that the objective function is convex, the proposed neural network is shown to be stable in the sense of Lyapunov and globally converges to the optimal solution of the original problem. Several numerical examples show the effectiveness of the proposed neural network.     

A new generic scheme for functional logic programming with constraints

In this paper we propose a new generic scheme CFLP풟, intended as a logical and semantic framework for lazy Constraint Functional Logic Programming over a parametrically given constraint domain 풟. As in the case of the well known CLP풟 scheme for Constraint Logic Programming, 풟 is assumed to provide domain specific data values and constraints. CFLP풟 programs are presented as sets of constrained rewrite rules that define the behavior of possibly higher order and/or non-deterministic lazy functions over 풟. As a main novelty w.r.t. previous related work, we present a Constraint Rewriting Logic CRWL풟 which provides a declarative semantics for CFLP풟 programs. This logic relies on a new formalization of constraint domains and program interpretations, which allows a flexible combination of domain specific data values and user defined data constructors, as well as a functional view of constraints. This research has been partially supported by the Spanish National Projects MELODIAS (TIC2002-01167), MERIT-FORMS (TIN2005-09207-C03-03) and PROMESAS-CAM (S-0505/TIC/0407).     

Efficient solution concepts and their application in uncertain multiobjective programming

Based on uncertainty theory, we investigate the relations among efficiency concepts of the multiobjective programming (MOP) with uncertain vectors. We first propose the uncertain MOP model, and study its convexity. Then, we define different efficiency concepts such as expected-value efficiency, expected-value proper efficiency, and establish their relations under the assumed conditions, which are illustrated through two numerical examples. Finally, in the uncertain environment, we apply the theoretical results to a redundancy allocation problem with two objectives in reparable parallel-series systems, and discuss how to obtain different types of efficient solutions according to the decision-maker's preferences.     

Learning linear PCA with convex semi-definite programming

The aim of this paper is to learn a linear principal component using the nature of support vector machines (SVMs). To this end, a complete SVM-like framework of linear PCA (SVPCA) for deciding the projection direction is constructed, where new expected risk and margin are introduced. Within this framework, a new semi-definite programming problem for maximizing the margin is formulated and a new definition of support vectors is established. As a weighted case of regular PCA, our SVPCA coincides with the regular PCA if all the samples play the same part in data compression. Theoretical explanation indicates that SVPCA is based on a margin-based generalization bound and thus good prediction ability is ensured. Furthermore, the robust form of SVPCA with a interpretable parameter is achieved using the soft idea in SVMs. The great advantage lies in the fact that SVPCA is a learning algorithm without local minima because of the convexity of the semi-definite optimization problems. To validate the performance of SVPCA, several experiments are conducted and numerical results have demonstrated that their generalization ability is better than that of regular PCA. Finally, some existing problems are also discussed.     

An approximate dynamic programming approach to convex quadratic knapsack problems

Quadratic knapsack problem (QKP) has a central role in integer and combinatorial optimization, while efficient algorithms to general QKPs are currently very limited. We present an approximate dynamic programming (ADP) approach for solving convex QKPs where variables may take any integer value and all coefficients are real numbers. We approximate the function value using (a) continuous quadratic programming relaxation (CQPR), and (b) the integral parts of the solutions to CQPR. We propose a new heuristic which adaptively fixes the variables according to the solution of CQPR. We report computational results for QKPs with up to 200 integer variables. Our numerical results illustrate that the new heuristic produces high-quality solutions to large-scale QKPs fast and robustly.     

Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time

In this paper, we consider single-machine scheduling problem in which processing time of a job is described by a convex decreasing resource consumption function. The objective is to minimize the total amount of resource consumed subject to a constraint on total weighted flow time. The optimal resource allocation is obtained for any arbitrary job sequence. The computational complexity of the general problem remains an open question, but we present and analyze some special cases that are solvable by using polynomial time algorithms. For the general problem, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions. The results show that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%.     

A projective method for linear programming with box-type constraints

A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.This work was done while the author was visiting New York University.     

Sharpe-ratio pricing and hedging of contingent claims in incomplete markets by convex programming

We analyze the problem of pricing and hedging contingent claims in a financial market described by a multi-period, discrete-time, finite-state scenario tree using an arbitrage-adjusted Sharpe-ratio criterion. We show that the writer’s and buyer’s pricing problems are formulated as conic convex optimization problems which allow to pass to dual problems over martingale measures and yield tighter pricing intervals compared to the interval induced by the usual no-arbitrage price bounds. An extension allowing proportional transaction costs is also given. Numerical experiments using S&P 500 options are given to demonstrate the practical applicability of the pricing scheme.     

Model and heuristic for berth allocation in tidal bulk ports with stock level constraints

We consider the problem of allocating berth positions for vessels in tidal bulk port terminals. A berth is defined as a specific location alongside a quay where a ship loader is available for loading or unloading vessels, accommodating only one vessel at a time. In tidal ports, draft conditions depend on high tide conditions, since available depth at low tide is not adequate for the movement of ships. Some port terminals are associated with important transnational enterprises which maintain strong control over the stock level of their goods. Since the stock level sometimes depends on a continuous process of consumption or production of minerals, the decision to load or unload vessels must consider the amount of the bulk cargo stored in the port yards. Therefore, a basic criterion for decision making is to give priority to the vessels related to the most critical mineral stock level. A second basic criterion is to decide what sequence of vessels reduces the overall demurrage within a given planning horizon. This paper presents an integer linear programming model based on the transportation problem to represent the Berth Allocation Problem in Tidal Bulk ports with Stock level conditions (BAPTBS). Problem instances are solved by a commercial solver and by a Simulated Annealing-based algorithm (SA). The SA employs a problem-specific heuristic, becoming a valid alternative for finding out good solutions for difficult instances.     

Fuzzy based fast dynamic programming solution of unit commitment with ramp constraints

Abstract: A fast dynamic programming technique based on a fuzzy based unit selection procedure is proposed in this paper for the solution of the unit commitment problem with ramp constraints. The curse of dimensionality of the dynamic programming technique is eliminated by minimizing the number of prospective solution paths to be stored at each stage of the search procedure. Heuristics like priority ordering of the units, unit grouping, fast economic dispatch based on priority ordering, and avoidance of repeated economic dispatch through memory action have been employed to make the algorithm fast. The proposed method produced comparable results with the best performing methods found in the literature.     

Continuum topology optimization with non-probabilistic reliability constraints based on multi-ellipsoid convex model

Using a quantified measure for non-probab ilistic reliability based on the multi-ellipsoid convex model, the topology optimization of continuum structures in presence of uncertain-but-bounded parameters is investigated. The problem is formulated as a double-loop optimization one. The inner loop handles evaluation of the non-probabilistic reliability index, and the outer loop treats the optimum material distribution using the results from the inner loop for checking feasibility of the reliability constraints. For circumventing the numerical difficulties arising from its nested nature, the topology optimization problem with reliability constraints is reformulated into an equivalent one with constraints on the concerned performance. In this context, the adjoint variable schemes for sensitivity analysis with respect to uncertain variables as well as design variables are discussed. The structural optimization problem is then solved by a gradient-based algorithm using the obtained sensitivity. In the present formulation, the uncertain-but bounded uncertain variations of material properties, geometrical dimensions and loading conditions can be realistically accounted for. Numerical investigations illustrate the applicability and the validity of the present problem statement as well as the proposed numerical techniques. The computational results also reveal that non-probabilistic reliability-based topology optimization may yield more reasonable material layouts than conventional deterministic approaches. The proposed method can be regarded as an attractive supplement to the stochastic reliability-based topology optimization.