Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities

This paper considers the optimization problem of minimizing a rational function. We reformulate this problem as a polynomial optimization problem by the technique of homogenization. These two problems are shown to be equivalent under some generic conditions. The exact Jacobian SDP relaxation method proposed by Nie is used to solve the resulting polynomial optimization problem. We also prove that the assumption of nonsingularity in Nie’s method can be weakened to the finiteness of singularities. Some numerical examples are given in the end.     

On difference of two monotone operators

In this paper, we introduce and consider the problem of finding zeroes of difference of two monotone operators in a Hilbert space. Using the resolvent operator technique, we show that this problem is equivalent to the fixed point problem. This equivalence is used to suggest and analyze an iterative method for finding a zero of difference of two monotone operators. We also discuss the convergence of the iterative method under suitable conditions. Our method of proof is very simple as compared with other techniques.     

Approximation of solutions to second order nonlinear Picard problems with Carathéodory right-hand side

We present an approximation method for Picard second order boundary value problems with Carathéodory righthand side. The method is based on the idea of replacing a measurable function in the right-hand side of the problem with its Kantorovich polynomial. We will show that this approximation scheme recovers essential solutions to the original BVP. We also consider the corresponding finite dimensional problem. We suggest a suitable mapping of solutions to finite dimensional problems to piecewise constant functions so that the later approximate a solution to the original BVP. That is why the presented idea may be used in numerical computations.     

Finite element methods of an operator splitting applied to population balance equations

In population balance equations, the distribution of the entities depends not only on space and time but also on their own properties referred to as internal coordinates. The operator splitting method is used to transform the whole time-dependent problem into two unsteady subproblems of a smaller complexity. The first subproblem is a time-dependent convection-diffusion problem while the second one is a transient transport problem with pure advection. We use the backward Euler method to discretize the subproblems in time. Since the first problem is convection-dominated, the local projection method is applied as stabilization in space. The transport problem in the one-dimensional internal coordinate is solved by a discontinuous Galerkin method. The unconditional stability of the method will be presented. Optimal error estimates are given. Numerical tests confirm the theoretical results.     

A method for maximizing matrix columns

We describe a singular-value decomposition method, where one-side rotation is used. The algorithm is also applied for a symmetrical spectral problem for matrices.     

Global classical solution of quasi-stationary Stefan free boundary problem

We consider an one-phase quasi-stationary Stefan problem (Hele–Shaw problem) in multidimensional case. Under some reasonable conditions we prove that the problem has a classical solution globally in time. The method can be used in two-phase problem as well. We also discuss asymptotic behavior of solution as t→+∞. The method developed here can be extended to a general class of free boundary problems.     

Finite element methods of an operator splitting applied to population balance equations

In population balance equations, the distribution of the entities depends not only on space and time but also on their own properties referred to as internal coordinates. The operator splitting method is used to transform the whole time-dependent problem into two unsteady subproblems of a smaller complexity. The first subproblem is a time-dependent convection–diffusion problem while the second one is a transient transport problem with pure advection. We use the backward Euler method to discretize the subproblems in time. Since the first problem is convection-dominated, the local projection method is applied as stabilization in space. The transport problem in the one-dimensional internal coordinate is solved by a discontinuous Galerkin method. The unconditional stability of the method will be presented. Optimal error estimates are given. Numerical tests confirm the theoretical results.     

Implementation of Some Methods of Shape Design for Variational Inequalities

In this paper we present some results concerning the optimal shape design problem governed by the fourth-order variational inequalities. The problem can be considered as a model example for the design of the shapes for elastic-plastic problem. The computations are done by finite element method, and the performance criterion is minimized by the material derivative method. We also discuss the error estimates in the appropriate norm and present some numerical results. An example is used to clearly illustrate the essential elements of shape design problems.     

The Budget Constrained Multi-Product Newsboy Problem with Reactive Production: A Problem from Entrepreneurial Network Construction

This paper develops an extended newsboy model and presents a formulation for this model. This new model has solved the budget contained multi-product newsboy problem with the reactive production. This model can be used to describe the status of entrepreneurial network construction. We use the Lagrange multiplier procedure to deal with our problem, but it is too complicated to get the exact solution. So we introduce the homotopy method to deal with it. We give the flow chart to describe how to get the solution via the homotopy method. We also illustrate our model in both the classical procedure and the homotopy method. Comparing the two methods, we can see that the homotopy method is more exact and efficient.     

SAA-regularized methods for multiproduct price optimization under the pure characteristics demand model

Utility-based choice models are often used to determine a consumer’s purchase decision among a list of available products; to provide an estimate of product demands; and, when data on purchase decisions or market shares are available, to infer consumers’ preferences over observed product characteristics. These models also serve as a building block in modeling firms’ pricing and assortment optimization problems. We consider a firm’s multiproduct pricing problem, in which product demands are determined by a pure characteristics model. A sample average approximation (SAA) method is used to approximate the expected market share of products and the firm profit. We propose an SAA-regularized method for the multiproduct price optimization problem. We present convergence analysis and numerical examples to show the efficiency and the effectiveness of the proposed method.     

Solving Examination Timetabling Problems through Adaption of Heuristic Orderings

Heuristic ordering based methods, very similar to those used for graph colouring problems, have long been applied successfully to the examination timetabling problem. Despite the success of these methods on real life problems, even with limited computing resources, the approach has the fundamental flaw that it is only as effective as the heuristic that is used. We present a method that adapts to suit a particular problem instance “on the fly.” This method provides an alternative to existing forms of ‘backtracking,’ which are often required to cope with the possible unsuitability of a heuristic. We present a range of experiments on benchmark problems to test and evaluate the approach. In comparison to other published approaches to solving this problem, the adaptive method is more general, significantly quicker and easier to implement and produces results that are at least comparable (if not better) than the current state of the art. We also demonstrate the level of generality of this approach by starting it with the inverse of a known good heuristic, a null ordering and random orderings, showing that the adaptive method can transform a bad heuristic ordering into a good one.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Machine Criticality Measures and Subproblem Solution Procedures in Shifting Bottleneck Methods: A Computational Study

We examine the effects of different machine criticality measures (MCMs) and subproblem solution procedures (SSPs) on the performance of Shifting Bottleneck (SB) methods for the problem of minimizing maximum lateness in a job shop. Extensive computational experiments show that for problems with balanced workloads and random routeings simple MCMs and SSPs can be used without affecting solution quality. Routeing structure affects the performance of the SB method significantly. We also find that, contrary to some previous studies, the problem of maintaining feasibility in the SB method is significant.     

A heuristic method for RCPSP with fuzzy activity times

In this paper, we propose a heuristic method for resource constrained project scheduling problem with fuzzy activity times. This method is based on priority rule for parallel schedule generation scheme. Calculation of critical path in this case requires comparison of fuzzy numbers. Distance based ranking of fuzzy number is used for finding the critical path length and concept of shifting criticality is proposed for some of the special cases. We also propose a measure for finding the non-integer power of a fuzzy number. We discuss some properties of the proposed method. We use an example to illustrate the method.     

On a hybrid method for a family of relatively nonexpansive mappings in a Banach space

We prove strong convergence theorems by the hybrid method given by Takahashi, Takeuchi, and Kubota for a family of relatively nonexpansive mappings under weaker conditions. The method of the proof is different from the original one and it shows that the type of projection used in the iterative method is independent of the properties of the mappings. We also deal with the problem of finding a zero of a maximal monotone operator and obtain a strong convergence theorem using this method.     

Analysis on a Finite Volume Element Method for Stokes Problems

Finite volume element method for the Stokes problem is considered. We use a conforming piecewise linear function on a fine grid for velocity and piecewise constant element on a coarse grid for pressure. For general triangulation we prove the equivalence of the finite volume element method and a saddle-point problem, the inf-sup condition and the uniqueness of the approximation solution. We also give the optimal order H^1 norm error estimate. For two widely used dual meshes we give the L^2 norm error estimates, which is optimal in one case and quasi-optimal in another ease. Finally we give a numerical example.     

A Level-Value Estimation Method and Stochastic Implementation for Global Optimization

In this paper, we propose a new method, namely the level-value estimation method, for finding global minimizer of continuous optimization problem. For this purpose, we define the variance function and the mean deviation function, both depend on a level value of the objective function to be minimized. These functions have some good properties when Newton’s method is used to solve a variance equation resulting by setting the variance function to zero. We prove that the largest root of the variance equation equals the global minimal value of the corresponding optimization problem. We also propose an implementable algorithm of the level-value estimation method where importance sampling is used to calculate integrals of the variance function and the mean deviation function. The main idea of the cross-entropy method is used to update the parameters of sample distribution at each iteration. The implementable level-value estimation method has been verified to satisfy the convergent conditions of the inexact Newton method for solving a single variable nonlinear equation. Thus, convergence is guaranteed. The numerical results indicate that the proposed method is applicable and efficient in solving global optimization problems.     

Infinite Element Approximation to Axial Symmetric Stokes Flow

We considered in [1] the finite element approximation to axial symmetric Stokes flow in a bounded domain. The problem for the flow passing an obstacle in an unbounded domain is also frequently encountered. In this paper, we are going to give approximate solutions for this problem by an approach stated in [2]. An iterative method is used to calculate the combined stiffness matrix.     

Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method

An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD) is considered. We propose a new heuristic method to solve the problem, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.