A primal–dual algorithm for the economic lot-sizing problem with multi-mode replenishment

The classical economic lot-sizing problem assumes that a single supplier and a single transportation mode are used to replenish the inventory. This paper studies an extension of this problem where several suppliers and transportation modes are available. The decision-making process in this case involves identifying (i) the timing for an order; (ii) the choice of shipment modes; and (iii) the order size for each mode. The problem is defined as a network flow problem with multiple setups cost function and additional side constraints. This study provides an MIP formulation for the problem. We also provide an additional formulation of the problem by redefining its decision variables and show that the dual of the corresponding LP-relaxation has a special structure. We take advantage of the structure of the dual problem to develop a primal–dual algorithm that generates tight lower and upper bounds. Computational results demonstrate the effectiveness of the algorithm.     

Deriving the Properties of Linear Bilevel Programming via a Penalty Function Approach

For the linear bilevel programming problem, we propose an assumption weaker than existing assumptions, while achieving similar results via a penalty function approach. The results include: equivalence between (i) existence of a solution to the problem, (ii) existence of an exact penalty function approach for solving the problem, and (iii) achievement of the optimal value of the equivalent form of the problem at some vertex of a certain polyhedral convex set. We prove that the assumption is both necessary and sufficient for the linear bilevel programming problem to admit an exact penalty function formulation, provided that the equivalent form of the problem has a feasible solution. A method is given for computing the minimal penalty function parameter value. This method can be executed by solving a set of linear programming problems. Lagrangian duality is also presented.     

Iteration method in a routing problem with internal losses

The problem of a sequential traversal of sets is considered, which is complicated by the necessity of fulfilling (internal) tasks on the sets as well as by constraints in the form of precedence conditions. It is assumed that the method of aggregating the expenses is additive. For the appearing extremal problem with dependent variables, an equivalent transformation to an optimization problem on a Cartesian product is proposed. Based on this, an iteration method is constructed that uses a reconstructible model of the courier problem (a traveling salesman problem complicated by precedence conditions).     

On the block upper-triangularity of undiscounted multi-chain markov decision problems

We show that the LP formulation for an undiscounted multi-chain Markov decision problem can be put in a block upper-triangular form by a polynomial time procedure. Each minimal block (after an appropriate dynamic revision) gives rise to a single-chain Markov decision problem which can be treated independently. An optimal solution to each single-chain problem can be connected by auxiliary dual programs to obtain an optimal solution to a multi-chain problem.     

Combinatorial Optimization by Dynamic Contraction

A heuristic optimization methodology, Dynamic Contraction (DC), is introduced as an approach for solving a wide variety of hard combinatorial problems. Contraction is an operation that maps an instance of a problem to a smaller instance of the same problem. DC is an iterative improvement strategy that relies on contraction as a mechanism for escaping local minima. As a byproduct of contraction, efficiency is improved due to a reduction of problem size. Effectiveness of DC is shown through simple applications to two classical combinatorial problems: The graph bisection problem and the traveling salesman problem.     

Problem of optimal endogenous growth with exhaustible resources and possibility of a technological jump

In 2013, S. Aseev, K. Besov, and S. Kaniovski (“The problem of optimal endogenous growth with exhaustible resources revisited,” Dyn. Model. Econometr. Econ. Finance 14, 3–30) considered the problem of optimal dynamic allocation of economic resources in an endogenous growth model in which both production and research sectors require an exhaustible resource as an input. The problem is formulated as an infinite-horizon optimal control problem with an integral constraint imposed on the control. A full mathematical study of the problem was carried out, and it was shown that the optimal growth is not sustainable under the most natural assumptions about the parameters of the model. In the present paper we extend the model by introducing an additional possibility of “random” transition (jump) to a qualitatively new technological trajectory (to an essentially unlimited backstop resource). As an objective functional to be maximized, we consider the expected value of the sum of the objective functional in the original problem on the time interval before the jump and an evaluation of the state of the model at the moment of the jump. The resulting problem also reduces to an infinite-horizon optimal control problem, and we prove an existence theorem for it and write down an appropriate version of the Pontryagin maximum principle. Then we characterize the optimal transitional dynamics and compare the results with those for the original problem (without a jump).     

Asymptotic solution method for a quasilinear minimum force control problem

For a transient process in a quasilinear system, we consider an optimization problem of finding a (multi-dimensional) control with minimum intensity. We suggest an algorithm for constructing asymptotic approximations to the solution of this problem. The main advantage of the algorithm is that an optimal control problem for a linear system is solved instead of the original essentially nonlinear problem.     

The inverse solution of the atomic mixing equations by an operator-splitting method

The quantification problem of recovering the original material distribution from secondary ion mass spectrometry (SIMS) data is considered in this paper. It is an inverse problem, is ill-posed and hence it requires a special technique for its solution. The quantification problem is essentially an inverse diffusion or (classically) a backward heat conduction problem. In this paper an operator-splitting method (that is proposed in a previous paper by the first author for the solution of inverse diffusion problems) is developed for the solution of the problem of recovering the original structure from the SIMS data. A detailed development of the quantification method is given and it is applied to typical data to demonstrate its effectiveness.     

Inverse sorting problem by minimizing the total weighted number of changes and partial inverse sorting problems

In this paper, we consider two types of inverse sorting problems. The first type is an inverse sorting problem by minimizing the total weighted number of changes with bound constraints. We present an O(n ²) time algorithm to solve the problem. The second type is a partial inverse sorting problem and a variant of the partial inverse sorting problem. We show that both the partial inverse sorting problem and the variant can be solved by a combination of a sorting problem and an inverse sorting problem. Supported by the Hong Kong Universities Grant Council (CERG CITYU 103105) and the National Key Research and Development Program of China (2002CB312004) and the National Natural Science Foundation of China (700221001, 70425004).     

A ring-mesh topology design problem for optical transport networks

This paper deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The problem seeks to find an optimal clustering of traffic demands in the network such that the total cost of optical add-drop multiplexer (OADM) and optical cross-connect (OXC) is minimized, while satisfying the OADM ring capacity constraint, the node cardinality constraint, and the OXC capacity constraint. We formulate the problem as an integer programming model and propose several alternative modeling techniques designed to improve the mathematical representation of the problem. We then develop various classes of valid inequalities to tighten the mathematical formulation of the problem and describe an algorithmic approach that coordinates tailored routines with a commercial solver CPLEX. We also propose an effective tabu search procedure for finding a good feasible solution as well as for providing a good incumbent solution for the column generation based heuristic procedure that enhances the solvability of the problem. Computational results exhibit the viability of the proposed method.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

所有点对之间最快路问题

所有点对之间最快路问题就是要在所有点对(Vs，Vt)之间传送数据δs,t,并找出一条最快的路线．解决所有点对之间最快路问题的关键是产生有效解的等价集合．运用动态点对最短路的算法，本文首先设计了一个时间复杂性为O(mn^2)的产生有效解等价集合的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂性分别为O(mn^2)和O(m^2n^2)．最后本文研究了求和对最小的路问题，证明该问题可以在O(mn^2)时间内解决．     

Evaluation model of problem solving

Problem solving is a style of thinking, which transforms a given problem to the goal state through a so-called PS (problem solving) path. Different from the traditional GPS (General Problem Solver) approach, the focus in this paper is placed on how to judge the performance of PS paths, that is, the evaluation problem of problem solving.A series of PS paths point from the given source problem to the destination goal, then form a PSN (PS Network). This paper proposes an elaborated CPSN (Coordinate Problem Solving Network) as the evaluation model of problem solving. In CPSN, each problem is assigned a unique coordinate and then each PS path can have an evaluation vector. Several examples show such arrangement can give more insight to PS paths.Furthermore, an incremental learning algorithm is developed for the update of CPSN. When a new PS path is obtained, it is not necessary to recalculate the whole CPSN. Examples show such algorithm provides a more efficient way in finding new PS paths.     

一类抛物型方程系数反问题的分裂算法

考虑利用终端时刻的温度u(x,T)=Z_T(x)反演热传导方程u_t-a~2u_(xx) q(x)u=0,x∈(0,1)中的未知系数q(x)的反问题.通过引进变换v(x,t)=(u_t(x,t)/u(x,t))将此非线性不适定问题的求解分解为两步.首先利用输入数据迭代求解一个非线性的正问题(该过程独立于未知系数),得到其迭代解v~(k)(x,t).其次利用q(x)与v(x,t)的关系式求出q(x)的近似解.对提出的反演方法,证明了采用的变换的可行性,得到了原反问题与由变换后的非线性正问题反演q(x)的等价性并且证明了迭代解的收敛性,给出了收敛速度.数值结果表明了该方法的有效性.     

Euler Discretization and Inexact Restoration for Optimal Control

A computational technique for unconstrained optimal control problems is presented. First, an Euler discretization is carried out to obtain a finite-dimensional approximation of the continuous-time (infinite-dimensional) problem. Then, an inexact restoration (IR) method due to Birgin and Martínez is applied to the discretized problem to find an approximate solution. Convergence of the technique to a solution of the continuous-time problem is facilitated by the convergence of the IR method and the convergence of the discrete (approximate) solution as finer subdivisions are taken. The technique is numerically demonstrated by means of a problem involving the van der Pol system; comprehensive comparisons are made with the Newton and projected Newton methods.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

The Steiner Problem on Surfaces of Revolution

While the Steiner problem has been extensively studied in the Euclidean plane, it remains an open problem to solve the Steiner problem on arbitrary non-planar (piecewise smooth) surfaces. We suggest an algorithm for solving the n-point Steiner problem on surfaces of revolution which have a non-decreasing generating function by constructing an isometric framework on a plane endowed with a weighted distance metric, thus propelling a new analytical avenue for studying the Steiner problem on surfaces with non-constant curvature.     

Filtration problem in inhomogeneous dam by using embedding method

This paper is devoted to a new numerical technique for the approximation of the flow problem of incompressible liquid through an inhomogeneous porous medium (say dam). First the problem is expressed as an optimal control problem governed by variational forms on a fixed domain. Then by using an embedding method, the class of admissible shapes is replaced by a class of positive Radon measures. The optimization problem in measure space is then approximated by a linear programming problem. The optimal measure representing optimal shape is approximated by the solution of this linear programming problem. Numerical example is also given.     

A penalty function method based on bilevel programming for solving inverse optimal value problems

In this work, we reformulate the inverse optimal value problem equivalently as a corresponding nonlinear bilevel programming (BLP) problem. For the nonlinear BLP problem, the duality gap of the lower level problem is appended to the upper level objective with a penalty, and then a penalized problem is obtained. On the basis of the concept of partial calmness, we prove that the penalty function is exact. Then, an algorithm is proposed and an inverse optimal value problem is resolved to illustrate the algorithm.     

Trust-region problems with linear inequality constraints: exact SDP relaxation,global optimality and robust optimization

The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.