Static and Dynamic Layout Problems with Varying Areas

This paper describes a two-step algorithm for solving the layout problem while assuming the departments can have varying areas. The first step solves a quadratic assignment problem formulation of the problem using a heuristic cutting plane routine. The second step solves a mixed-integer linear programming prob- lem to find the desired block diagram layout. The algorithm incorporates two concepts to make the solu- tions more practical. First, rearrangement costs are simultaneously considered along with flow costs in solving a dynamic layout problem involving multiple time periods. It is the only algorithm to solve a general dynamic layout problem with varying department areas. Second, regular department shapes are maintained by requiring all departments to be rectangular. Its formulation for doing this is more efficient than previous algorithms.     

The Multi-Story Space Assignment Problem

The Multi-Story Space Assignment Problem (MSAP) is an innovative formulation of the multi-story facility assignment problem that allows one to model the location of departments of unequal size within multi-story facilities as a Generalized Quadratic 3-dimensional Assignment Problem (GQ3AP). Not only can the MSAP generate the design of the location of the departments in the facility, the MSAP also includes the evacuation planning for the facility. The formulation, background mathematical development, and computational experience with a branch and bound algorithm for the MSAP are also presented.     

An improved two-stage optimization-based framework for unequal-areas facility layout

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present an improved optimization-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical optimization models. The first model is a nonlinear approximation of the problem that establishes the relative position of the departments within the facility, and the second model is an exact convex optimization formulation of the problem that determines the final layout. Aspect ratio constraints on the departments are taken into account by both models. Our computational results show that the proposed framework is computationally efficient and consistently produces competitive, and often improved, layouts for well-known instances from the literature as well as for new large-scale instances with up to 100 departments.     

Heuristics for the dynamic facility layout problem with unequal-area departments

The dynamic facility layout problem (DFLP) is the problem of finding positions of departments on the plant floor for multiple periods (material flows between departments change during the planning horizon) such that departments do not overlap, and the sum of the material handling and rearrangement costs is minimized. In this paper, the departments may have unequal-areas and free orientations, and the layout for each period is generated on the continuous plant floor. Because of the complexity of the problem, only small-size problems can be solved in reasonable time using exact techniques. As a result, a boundary search (construction) technique, which places departments along the boundaries of already placed departments, is developed for the DFLP. The solution is improved using a tabu search heuristic. The heuristics were tested on some instances from the DFLP and static facility layout problem (SFLP) literature. The results obtained demonstrate the effectiveness of the heuristics.     

Multicommodity network flows: The impact of formulation on decomposition

This paper investigates the impact of problem formulation on Dantzig—Wolfe decomposition for the multicommodity network flow problem. These problems are formulated in three ways: origin-destination specific, destination specific, and product specific. The path-based origin-destination specific formulation is equivalent to the tree-based destination specific formulation by a simple transformation. Supersupply and superdemand nodes are appended to the tree-based product specific formulation to create an equivalent path-based product specific formulation. We show that solving the path-based problem formulations by decomposition results in substantially fewer master problem iterations and lower CPU times than by using decomposition on the equivalent tree-based formulations. Computational results on a series of multicommodity network flow problems are presented.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

Equality Constraints in Multiobjective Robust Design Optimization: Decision Making Problem

Robust design optimization (RDO) problems can generally be formulated by incorporating uncertainty into the corresponding deterministic problems. In this context, a careful formulation of deterministic equality constraints into the robust domain is necessary to avoid infeasible designs under uncertain conditions. The challenge of formulating equality constraints is compounded in multiobjective RDO problems. Modeling the tradeoffs between the mean of the performance and the variation of the performance for each design objective in a multiobjective RDO problem is itself a complex task. A judicious formulation of equality constraints adds to this complexity because additional tradeoffs are introduced between constraint satisfaction under uncertainty and multiobjective performance. Equality constraints under uncertainty in multiobjective problems can therefore pose a complicated decision making problem. In this paper, we provide a new problem formulation that can be used as an effective multiobjective decision making tool, with emphasis on equality constraints. We present two numerical examples to illustrate our theoretical developments.     

A NEW DETERMINISTIC FORMULATION FOR DYNAMIC STOCHASTIC PROGRAMMING PROBLEMS AND ITS NUMERICAL COMPARISON WITH OTHERS

A new deterministic formulation, called the conditional expectation formulation, is proposed for dynamic stochastic programming problems in order to overcome some disadvantages of existing deterministic formulations. We then check the impact of the new deterministic formulation and other two deterministic formulations on the corresponding problem size, nonzero elements and solution time by solving some typi     

Optimal compromise solution of multi-objective minimal cost flow problems in fuzzy environment

Ghatee and Hashemi [M. Ghatee, S.M. Hashemi, Ranking function-based solutions of fully fuzzified minimal cost flow problem, Inform. Sci. 177 (2007) 4271–4294] transformed the fuzzy linear programming formulation of fully fuzzy minimal cost flow (FFMCF) problems into crisp linear programming formulation and used it to find the fuzzy optimal solution of balanced FFMCF problems. In this paper, it is pointed out that the method for transforming the fuzzy linear programming formulation into crisp linear programming formulation, used by Ghatee and Hashemi, is not appropriate and a new method is proposed to find the fuzzy optimal solution of multi-objective FFMCF problems. The proposed method can also be used to find the fuzzy optimal solution of single-objective FFMCF problems. To show the application of proposed method in real life problems an existing real life FFMCF problem is solved.     

Formulation of Euler-Lagrange equations for fractional variational problems

This paper presents extensions to traditional calculus of variations for systems containing fractional derivatives. The fractional derivative is described in the Riemann-Liouville sense. Specifically, we consider two problems, the simplest fractional variational problem and the fractional variational problem of Lagrange. Results of the first problem are extended to problems containing multiple fractional derivatives and unknown functions. For the second problem, we also present a Lagrange type multiplier rule. For both problems, we develop the Euler-Lagrange type necessary conditions which must be satisfied for the given functional to be extremum. Two problems are considered to demonstrate the application of the formulation. The formulation presented and the resulting equations are very similar to those that appear in the field of classical calculus of variations.     

A boundary integral formulation of the Stefan problem

This paper considers a boundary integral formulation of the Stefan problem for two spatial dimensions. This formulation has the advantage that its numerical implementation does not require the discretization of the Stefan condition. Furthermore, the formulation is capable of solving problems with complex boundaries. Several illustrative examples are given.     

Continuous quadratic programming formulations of optimization problems on graphs

Four NP-hard optimization problems on graphs are studied: The vertex separator problem, the edge separator problem, the maximum clique problem, and the maximum independent set problem. We show that the vertex separator problem is equivalent to a continuous bilinear quadratic program. This continuous formulation is compared to known continuous quadratic programming formulations for the edge separator problem, the maximum clique problem, and the maximum independent set problem. All of these formulations, when expressed as maximization problems, are shown to follow from the convexity properties of the objective function along the edges of the feasible set. An algorithm is given which exploits the continuous formulation of the vertex separator problem to quickly compute approximate separators. Computational results are given.     

Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications

This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush–Kuhn–Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a deterministic formulation called the expected residual minimization formulation for SSOCCP. We present an approximation method based on the Monte Carlo approximation techniques and investigate some properties related to existence of solutions of the ERM formulation. Furthermore, we experiment some practical applications, which include a stochastic natural gas transmission problem and a stochastic optimal power flow problem in radial network.     

Unconstrained 0–1 nonlinear programming: A nondifferentiable approach

The purpose of this paper is to give new formulations for the unconstrained 0–1 nonlinear problem. The unconstrained 0–1 nonlinear problem is reduced to nonlinear continuous problems where the objective functions are piecewise linear. In the first formulation, the objective function is a difference of two convex functions while the other formulations lead to concave problems. It is shown that the concave problems we obtain have fewer integer local minima than has the classical concave formulation of the 0–1 unconstrained 0–1 nonlinear problem.     

A mixed integer programming formulation for the 1-maximin problem

In this paper, I present a mixed integer programming (MIP) formulation for the 1-maximin problem with rectilinear distance. The problem mainly appears in facility location while trying to locate an undesirable facility. The rectilinear distance is quite commonly used in the location literature. Our numerical experiments show that one can solve reasonably large location problems using a standard MIP solver. We also provide a linear programming formulation that helps find an upper bound on the objective function value of the 1-maximin problem with any norm when extreme points of the feasible region are known. We discuss various extension alternatives for the MIP formulation.     

On generalized formulation of the equilibrium problem of an elastic strip

A “nonenergetic” formulation of the boundary value problems of statics of an elastic strip based on the principle of admissible displacements, is studied. The formulation makes possible, in particular, the study of problems concerning the strips of infinite energy, while retaining the external form of the “energetic” formulation /1–3/, and produces unique solvability of the problem under weaker restrictions imposed on the external loads. Such a formulation is also possible for other problems of the theory of elasticity.     

Moment calculations for piecewise-defined functions: an application to stochastic optimization with coherent risk measures

This work introduces a new analytical approach to the formulation of optimization problems with piecewise-defined (PD) objective functions. First, we introduce a new definition of multivariate PD functions and derive formal results for their continuity and differentiability. Then, we obtain closed-form expressions for the calculation of their moments. We apply these findings to three classes of optimization problems involving coherent risk measures. The method enables one to obtain insights on problem structure and on sensitivity to imprecision at the problem formulation stage, eliminating reliance on ad-hoc post-optimality numerical calculations.     

二阶退化双曲型方程的Darboux型问题

本文讨论二阶退化双曲型方程的一些边值问题.文中先给出第一Darboux问题和一般斜微商边值问题的提法和解的表示式,然后使用复分析方法证明了上述问题解的存在唯一性.     

A polyhedral study of triplet formulation for single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.     

三维定常流Stokes问题的边界积分方程法

1.解的积分表示及变分公式 考虑如下Stokes方程的Dirichlet问题:设Ω是具有光滑边界Γ的单连通区域,Ω′=R~3-Ω。所求未知量是充满于Ω或Ω′的不可压缩粘性流体的流速u=(u_1,u_2,u_3)和压力p。这里v是运动粘性系数。 已经证明[Nedelec-Communication personnelle]:若u_0∈(H~(1/2)(Γ))~3,且满足     

A Center Cutting Plane Algorithm for a Likelihood Estimate Problem

We describe a method for solving the maximum likelihood estimate problem of a mixing distribution, based on an interior cutting plane algorithm with cuts through analytic centers. From increasingly refined discretized statistical problem models we construct a sequence of inner non-linear problems and solve them approximately applying a primal-dual algorithm to the dual formulation. Refining the statistical problem is equivalent to adding cuts to the inner problems.