一类带延迟策略的库存优化模型及其仿真

考虑一类带延迟策略的库存优化模型, 即二层整数规划问题。证明了该二层整数规划问题等价于约束单层整数规划问题。借助罚函数思想化约束整数规划问题为无约束整数规划问题, 再利用遗传算法进行求解。数值模拟表明所得数值结果与已有的数值结果相比,不仅使得供应链整体库存效益有较大提高, 并且对每个库存分点的最优库存量作了更为合理的调整。     

A DC programming approach for planning a multisensor multizone search for a target

In this paper, we consider a well-known problem in the general area of search theory: planning a multisensor in multizone search so as to maximize the probability of detection of a target under a given resource effort to be shared. We propose a new optimization model that is a nonlinear mixed 0–1 programming problem. This problem is then reformulated as a DC (Difference of Convex) functions program via an exact penalty technique. DC programming and DCA (DC algorithm) have been investigated for solving the resulting DC program. Numerical experiments demonstrate the efficiency and the superiority of the proposed algorithm in comparison with the existing method.     

A continuous DC programming approach for resource allocation in OFDMA/TDD wireless networks

The next generation broadband wireless networks deploys OFDM/OFDMA as the enabling technologies for broadband data transmission with QoS capabilities. Many optimization problems have arisen in the conception of such a network. This article studies an optimization problem in resource allocation. By using mathematical modeling technique we formulate the considered problem as a pure integer linear program. This problem is reformulated as a DC (Difference of Convex functions) program via an exact penalty technique. We then propose a continuous approach for its resolution. Our approach is based on DC programming and DCA (DC Algorithm). It works in a continuous domain, but provides integer solutions. To check globality of computed solutions, a global method combining DCA with a well adapted Branch-and-Bound (B&B) algorithm is investigated. Preliminary numerical results are reported to show the efficiency of the proposed method with respect to the standard Branch-and-Bound algorithm.     

An interactive approach based on a discrete differential evolution algorithm for a class of integer bilevel programming problems

This paper presents an interactive approach based on a discrete differential evolution algorithm to solve a class of integer bilevel programming problems, in which integer decision variables are controlled by an upper-level decision maker and real-value or continuous decision variables are controlled by a lower-level decision maker. Using the Karush--Kuhn–Tucker optimality conditions in the lower-level programming, the original discrete bilevel formulation can be converted into a discrete single-level nonlinear programming problem with the complementarity constraints, and then the smoothing technique is applied to deal with the complementarity constraints. Finally, a discrete single-level nonlinear programming problem is obtained, and solved by an interactive approach. In each iteration, for each given upper-level discrete variable, a system of nonlinear equations including the lower-level variables and Lagrange multipliers is solved first, and then a discrete nonlinear programming problem only with inequality constraints is handled by using a discrete differential evolution algorithm. Simulation results show the effectiveness of the proposed approach.     

DC programming and DCA for enhancing physical layer security via cooperative jamming

The explosive development of computational tools these days is threatening security of cryptographic algorithms, which are regarded as primary traditional methods for ensuring information security. The physical layer security approach is introduced as a method for both improving confidentiality of the secret key distribution in cryptography and enabling the data transmission without relaying on higher-layer encryption. In this paper, the cooperative jamming paradigm - one of the techniques used in the physical layer is studied and the resulting power allocation problem with the aim of maximizing the sum of secrecy rates subject to power constraints is formulated as a nonconvex optimization problem. The objective function is a so-called DC (Difference of Convex functions) function, and some constraints are coupling. We propose a new DC formulation and develop an efficient DCA (DC Algorithm) to deal with this nonconvex program. The DCA introduces the elegant concept of approximating the original nonconvex program by a sequence of convex ones: at each iteration of DCA requires solution of a convex subproblem. The main advantage of the proposed approach is that it leads to strongly convex quadratic subproblems with separate variables in the objective function, which can be tackled by both distributed and centralized methods. One of the major contributions of the paper is to develop a highly efficient distributed algorithm to solve the convex subproblem. We adopt the dual decomposition method that results in computing iteratively the projection of points onto a very simple structural set which can be determined by an inexpensive procedure. The numerical results show the efficiency and the superiority of the new DCA based algorithm compared with existing approaches.     

Solving the hazmat transport network design problem

In this paper, we consider the problem of network design for hazardous material transportation where the government designates a network, and the carriers choose the routes on the network. We model the problem as a bilevel network flow formulation and analyze the bilevel design problem by comparing it to three other decision scenarios. The bilevel model is difficult to solve and may be ill-posed. We propose a heuristic solution method that always finds a stable solution. The heuristic exploits the network flow structure at both levels to overcome the difficulty and instability of the bilevel integer programming model. Testing on real data shows that the linearization of the bilevel model fails to find stable solutions and that the heuristic finds lower risk networks in less time. Further testing on random instances shows that the heuristically designed networks achieve significant risk reduction over single-level models. The risk is very close to the least risk possible. However, this reduction in risk comes with a significant increase in cost. We extend the bilevel model to account for the cost/risk trade-off by including cost in the first-level objective. The biobjective–bilevel model is a rich decision-support tool that allows for the generation of many good solutions to the design problem.     

Monthly tour scheduling models with mixed skills considering weekend off requirements

Unlike manufacturing, where standard shifts and days off are the rule, the service industry operates every day of the week across a month and a year. To maintain the morale and productivity of the workers in the service industry, the weekend off requirements, one of the important work preferences for the workers, should be respected and balanced for a longer planning horizon beyond a week. This paper deals with the monthly tour scheduling problem with mixed skills considering the weekend off requirements in contrast to the weekly planning horizon that is typical in most literature. The objective is to obtain the most economical mix of types of workers satisfying the patterns of demands for the workers and desired work characteristics. Two model formulations are developed based on implicit programming techniques. One model uses a general integer programming (GIP) formulation and assigns the lunch break hours aggregately to the workers based on the worker types. The other one adopts a binary integer programming (BIP) formulation and assigns the lunch break hours explicitly to the individual workers. The effectiveness of the two models is illustrated by the numerical tests and the results show that the BIP formulation is more efficient than the GIP formulation.     

An efficient k-means clustering algorithm: analysis andimplementation

In k-means clustering, we are given a set of n data points in d-dimensional space R^d and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation     

A perspective-based convex relaxation for switched-affine optimal control

We consider the switched-affine optimal control problem, i.e., the problem of selecting a sequence of affine dynamics from a finite set in order to minimize a sum of convex functions of the system state. We develop a new reduction of this problem to a mixed-integer convex program (MICP), based on perspective functions. Relaxing the integer constraints of this MICP results in a convex optimization problem, whose optimal value is a lower bound on the original problem value. We show that this bound is at least as tight as similar bounds obtained from two other well-known MICP reductions (via conversion to a mixed logical dynamical system, and by generalized disjunctive programming), and our numerical study indicates it is often substantially tighter. Using simple integer-rounding techniques, we can also use our formulation to obtain an upper bound (and corresponding sequence of control inputs). In our numerical study, this bound was typically within a few percent of the optimal value, making it attractive as a stand-alone heuristic, or as a subroutine in a global algorithm such as branch and bound. We conclude with some extensions of our formulation to problems with switching costs and piecewise affine dynamics.     

DC programming and DCA for solving Brugnano–Casulli piecewise linear systems

Piecewise linear optimization is one of the most frequently used optimization models in practice, such as transportation, finance and supply-chain management. In this paper, we investigate a particular piecewise linear optimization that is optimizing the norm of piecewise linear functions (NPLF). Specifically, we are interested in solving a class of Brugnano–Casulli piecewise linear systems (PLS), which can be reformulated as an NPLF problem. Speaking generally, the NPLF is considered as an optimization problem with a nonsmooth, nonconvex objective function. A new and efficient optimization approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) is developed. With a suitable DC formulation, we design a DCA scheme, named ℓ₁-DCA, for the problem of optimizing the ℓ₁-norm of NPLF. Thanks to particular properties of the problem, we prove that under some conditions, our proposed algorithm converges to an exact solution after a finite number of iterations. In addition, when a nonglobal solution is found, a numerical procedure is introduced to find a feasible point having a smaller objective value and to restart ℓ₁-DCA at this point. Several numerical experiments illustrate these interesting convergence properties. Moreover, we also present an application to the free-surface hydrodynamic problem, where the correct numerical modeling often requires to have the solution of special PLS, with the aim of showing the efficiency of the proposed method.     

Integrated Inventory Control and Facility Location Decisions in a Multi-Echelon Supply Chain Network with Hubs

This paper develops mathematical models to coordinate facility location and inventory control for a four-echelon supply chain network consisting of multiple suppliers, warehouses, hubs and retailers. The hubs help in reducing transportation costs by consolidating products from multiple warehouses and directing the larger shipments to the retailer. The integrated models studied in this paper simultaneously determines three types of decisions: (i) facility location—the number and location of warehouses and hubs, (ii) allocation—assignment of suppliers to located warehouses and retailers to located warehouses via the location hubs, and (iii) inventory control decisions at each located warehouse. The goal is to minimize the facility location, transportation and the inventory costs. A mixed integer nonlinear programming formulation is first presented. The nonlinear integer programming formulation is then transformed into a conic mixed integer program and a novel and compact conic mixed integer programming formulation. Computational runs are conducted using commercial solvers to compare the performance of the different formulations. The compact conic mixed integer programming formulation was found to significantly outperform the other formulations by achieving significant computational savings. The results demonstrate that large scale instances of certain multi-echelon supply chain network design problems can be solved using commercial solvers through intelligent reformulation of the model.     

Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective

In this paper, we minimize the weighted and unweighted number of tardy jobs on a single batch processing machine with incompatible job families. We propose two different mixed integer linear programming (MILP) formulations based on positional variables. The second formulation does not contain a big-M coefficient. Two iterative schemes are discussed that are able to provide tighter linear programming bounds by reducing the number of positional variables. Furthermore, we also suggest a random key genetic algorithm (RKGA) to solve this scheduling problem. Results of computational experiments are shown. The second MILP formulation is more efficient with respect to lower bounds, while the first formulation provides better upper bounds. The iterative scheme is effective for the weighted case. The RKGA is able to find high-quality solutions in a reasonable amount of time.     

An exact algorithm for the bilevel mixed integer linear programming problem under three simplifying assumptions

We present an exact algorithm for the bilevel mixed integer linear programming (BMILP) problem under three simplifying assumptions. Although BMILP has been studied for decades and widely applied to various real world problems, there are only a few BMILP algorithms. Compared to these existing ones, our new algorithm relies on fewer and weaker assumptions, explicitly considers finite optimal, infeasible, and unbounded cases, and is proved to terminate finitely and correctly. We report results of our computational experiments on a small library of BMILP test instances, which we created and made publicly available online.     

A location–inventory supply chain problem: Reformulation and piecewise linearization

In this paper, we study a two-echelon inventory management problem with multiple warehouses and retailers. The problem is a natural extension to the well-known one-warehouse multi-retailer inventory problem. The problem is formulated as a mixed integer non-linear program such that its continuous relaxation is non-convex. We propose an equivalent formulation with fewer non-linear terms in the objective function so that the continuous relaxation of the new model is a convex optimization problem. We use piecewise linearization to transform the resulting MINLP to a mixed integer program and we solve it using CPLEX. Through numerical experiments, we compare the solutions obtained by solving the new formulation using CPLEX with two previously published Lagrangian relaxation based heuristics to solve the original mixed integer non-linear program. We demonstrate that the new approach is capable of providing almost the same solutions without the need of using specialized algorithms. This important contribution further implies that additional variants of the problem, such as multiple products, capacitated warehouses and routing, can be added to result in a problem that will again be solvable by commercial optimization software, while the respective Lagrangian heuristics will fail to solve such variants or extended problems.     

两层多目标规划的罚函数法

研究了一类非线性两层多目标规划问题.在下层多目标规划问题的目标函数是严格凸函 数、决策变量约束集是凸集的假设下,通过将两层多目标规划问题转化成一系列单层多目标规划 问题,建立了两层多目标规划的罚函数理论,并进行了收敛性分析.从而丰富了两层多目标规划的 理论,为解决实际中的两层多目标决策问题提供了有力的工具.     

Exact methods and a heuristic for the optimization of an integrated replenishment-storage planning problem

In this paper we study the coordination of different activities in a supply chain issued from a real case. Multiple suppliers send raw materials (RMs) to a distribution center (DC) that delivers them to a unique plant where the storage of the RMs and the finished goods is not possible. Then, the finished goods are directly shipped to multiple customers having just‐in‐time (JIT) demands. Under these hypotheses, we show that the problem can be reduced to multiple suppliers and one DC. Afterwards, we analyze two cases; in the first, we consider an uncapacitated storage at DC, and in the second, we analyze the capacitated storage case. For the first case, we show that the problem is NP‐hard in the ordinary sense using the Knapsack decision problem. We then propose two exact methods: a mixed integer linear program (MILP) and a pseudopolynomial dynamic program. A classical dynamic program and an improved one using the idea of Shaw and Wagelmans are given. With numerical tests we show that the dynamic program gives the optimal solution in reasonable time for quite large instances compared with the MILP. For the second case, the capacity limitation in DC is assumed, which makes the problem solving more challenging. We propose an MILP and a dynamic programming‐based heuristic that provides solutions close to the optimal solution in very short times.     

A strategic model for supply chain design with logical constraints: formulation and solution

This paper proposes a strategic production–distribution model for supply chain design with consideration of bills of materials (BOM). Logical constraints are used to represent BOM and the associated relationships among the main entities of a supply chain such as suppliers, producers, and distribution centers. We show how these relationships are formulated as logical constraints in a mixed integer programming (MIP) model, thus capturing the role of BOM in the selection of suppliers in the strategic design of a supply chain. A test problem is presented to illustrate the effectiveness of the formulation and solution strategy. The results and their managerial implications are discussed.Scope and purposeSupply chain design is to provide an optimal platform for efficient and effective supply chain management. The problem is often an important and strategic operations management problem in supply chain management. This paper shows how the mixed integer programming modeling techniques can be applied to supply chain design problem, where some complicated relations, such as bills of materials, are involved. We discuss how to solve such a complicated model efficiently.     

Solving the minimum sum-of-squares clustering problem by hyperbolic smoothing and partition into boundary and gravitational regions

This article considers the minimum sum-of-squares clustering (MSSC) problem. The mathematical modeling of this problem leads to a min-sum-min formulation which, in addition to its intrinsic bi-level nature, has the significant characteristic of being strongly nondifferentiable. To overcome these difficulties, the proposed resolution method, called hyperbolic smoothing, adopts a smoothing strategy using a special C^∞ differentiable class function. The final solution is obtained by solving a sequence of low dimension differentiable unconstrained optimization subproblems which gradually approach the original problem. This paper introduces the method of partition of the set of observations into two nonoverlapping groups: “data in frontier” and “data in gravitational regions”. The resulting combination of the two methodologies for the MSSC problem has interesting properties, which drastically simplify the computational tasks.     

Contact shape optimization: a bilevel programming approach

We consider the problem of shape optimization of nonlinear elastic solids in contact. The equilibrium of the solid is defined by a constrained minimization problem, where the body energy functional is the objective and the constraints impose the nonpenetration condition. Then the optimization problem can be formulated in terms of a bilevel mathematical program. We describe new optimality conditions for bilevel programming and construct an algorithm to solve these conditions based on Herskovits’ feasible direction interior point method. With this approach we simultaneously carry out shape optimization and nonlinear contact analysis. That is, the present method is a “one shot” technique. We describe some numerical examples solved in a very efficient way. Received July 27, 1999     

Self-organizing maps by difference of convex functions optimization

We offer an efficient approach based on difference of convex functions (DC) optimization for self-organizing maps (SOM). We consider SOM as an optimization problem with a nonsmooth, nonconvex energy function and investigated DC programming and DC algorithm (DCA), an innovative approach in nonconvex optimization framework to effectively solve this problem. Furthermore an appropriate training version of this algorithm is proposed. The numerical results on many real-world datasets show the efficiency of the proposed DCA based algorithms on both quality of solutions and topographic maps.