Approximate algorithms for the competitive facility location problem

We consider the competitive facility location problem in which two competing sides (the Leader and the Follower) open in succession their facilities, and each consumer chooses one of the open facilities basing on its own preferences. The problem amounts to choosing the Leader’s facility locations so that to obtain maximal profit taking into account the subsequent facility location by the Follower who also aims to obtain maximal profit. We state the problem as a two-level integer programming problem. A method is proposed for calculating an upper bound for the maximal profit of the Leader. The corresponding algorithm amounts to constructing the classical maximum facility location problem and finding an optimal solution to it. Simultaneously with calculating an upper bound we construct an initial approximate solution to the competitive facility location problem. We propose some local search algorithms for improving the initial approximate solutions. We include the results of some simulations with the proposed algorithms, which enable us to estimate the precision of the resulting approximate solutions and give a comparative estimate for the quality of the algorithms under consideration for constructing the approximate solutions to the problem.     

A capacitated competitive facility location problem

We consider a mathematical model similar in a sense to competitive location problems. There are two competing parties that sequentially open their facilities aiming to “capture” customers and maximize profit. In our model, we assume that facilities’ capacities are bounded. The model is formulated as a bilevel integer mathematical program, and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as that of maximization of a pseudo-Boolean function with the number of arguments equal to the number of places available for facility opening. We propose an algorithm for calculating an upper bound for values that the function takes on subsets which are specified by partial (0, 1)-vectors.     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

Upper and lower bounding procedures for the multiple knapsack assignment problem

We formulate the multiple knapsack assignment problem (MKAP) as an extension of the multiple knapsack problem (MKP), as well as of the assignment problem. Except for small instances, MKAP is hard to solve to optimality. We present a heuristic algorithm to solve this problem approximately but very quickly. We first discuss three approaches to evaluate its upper bound, and prove that these methods compute an identical upper bound. In this process, reference capacities are derived, which enables us to decompose the problem into mutually independent MKPs. These MKPs are solved euristically, and in total give an approximate solution to MKAP. Through numerical experiments, we evaluate the performance of our algorithm. Although the algorithm is weak for small instances, we find it prospective for large instances. Indeed, for instances with more than a few thousand items we usually obtain solutions with relative errors less than 0.1% within one CPU second.     

A competitive hub location and pricing problem

We formulate and solve a new hub location and pricing problem, describing a situation in which an existing transportation company operates a hub and spoke network, and a new company wants to enter into the same market, using an incomplete hub and spoke network. The entrant maximizes its profit by choosing the best hub locations and network topology and applying optimal pricing, considering that the existing company applies mill pricing. Customers’ behavior is modeled using a logit discrete choice model. We solve instances derived from the CAB dataset using a genetic algorithm and a closed expression for the optimal pricing. Our model confirms that, in competitive settings, seeking the largest market share is dominated by profit maximization. We also describe some conditions under which it is not convenient for the entrant to enter the market.     

Fuzzy profit measures for a fuzzy economic order quantity model

Changing economic conditions make the selling price and demand quantity more and more uncertain in the market. The conventional inventory models determine the selling price and order quantity for a retailer’s maximal profit with exactly known parameters. This paper develops a solution method to derive the fuzzy profit of the inventory model when the demand quantity and unit cost are fuzzy numbers. Since the parameters contained in the inventory model are fuzzy, the profit value calculated from the model should be fuzzy as well. Based on the extension principle, the fuzzy inventory problem is transformed into a pair of two-level mathematical programs to derive the upper bound and lower bound of the fuzzy profit at possibility level α. According to the duality theorem of geometric programming, the pair of two-level mathematical programs is transformed into a pair of conventional geometric programs to solve. By enumerating different α values, the upper bound and lower bound of the fuzzy profit are collected to approximate the membership function. Since the profit of the inventory problem is expressed by the membership function rather than by a crisp value, more information is provided for making decisions.     

An approximate solution for linear boundary-value problems with slowly varying coefficients

In this paper, an approximate closed-form solution for linear boundary-value problems with slowly varying coefficient matrices is obtained. The derivation of the approximate solution is based on the freezing technique, which is commonly used in analyzing the stability of slowly varying initial-value problems as well as solving them. The error between the approximate and the exact solutions is given, and an upper bound on the norm of the error is obtained. This upper bound is proportional to the rate of change of the coefficient matrix of the boundary-value problem. The proposed approximate solution is obtained for a two-point boundary-value problem and is compared to its solution obtained numerically. Good agreement is observed between the approximate and the numerical solutions, when the rate of change of the coefficient matrix is small.     

Global Complexity Bound Analysis of the Levenberg–Marquardt Method for Nonsmooth Equations and Its Application to the Nonlinear Complementarity Problem

We investigate a global complexity bound of the Levenberg–Marquardt Method (LMM) for nonsmooth equations. The global complexity bound is an upper bound to the number of iterations required to get an approximate solution that satisfies a certain condition. We give sufficient conditions under which the bound of the LMM for nonsmooth equations is the same as smooth cases. We also show that it can be reduced under some regularity assumption. Furthermore, by applying these results to nonsmooth equations equivalent to the nonlinear complementarity problem (NCP), we get global complexity bounds for the NCP. In particular, we give a reasonable bound when the mapping involved in the NCP is a uniformly P-function.     

Optimal lot size and inspection policy for products sold with warranty

This paper develops a mathematical model to jointly determine the optimal lot size and product inspection policy for a deteriorating production system, when products are sold with free minimal repair warranty. Due to system deterioration, a last-K product inspection scheme is proposed, under which the last K products in a production lot are inspected and nonconforming products found are reworked. Based on the model, we show that there exist a unique optimal lot size and a corresponding inspection policy such that the expected total cost per unit time is minimized. Since there is no closed-form expression for the optimal lot size, an upper bound and approximate solutions are obtained to facilitate the search process. Furthermore, an algorithm is provided to efficiently search for the optimal policy and the performance of the optimal policy is evaluated through numerical examples.     

An upper bound for the competitive location and capacity choice problem with multiple demand scenarios

A new mathematical model is considered related to competitive location problems where two competing parties, the Leader and the Follower, successively open their facilities and try to win customers. In the model, we consider a situation of several alternative demand scenarios which differ by the composition of customers and their preferences.We assume that the costs of opening a facility depend on its capacity; therefore, the Leader, making decisions on the placement of facilities, must determine their capacities taking into account all possible demand scenarios and the response of the Follower. For the bilevel model suggested, a problem of finding an optimistic optimal solution is formulated. We show that this problem can be represented as a problem of maximizing a pseudo- Boolean function with the number of variables equal to the number of possible locations of the Leader’s facilities.We propose a novel systemof estimating the subsets that allows us to supplement the estimating problems, used to calculate the upper bounds for the constructed pseudo-Boolean function, with additional constraints which improve the upper bounds.     

基于可信性分布的投资组合问题的一种混合智能方法

研究了模糊环境下基于效用函数的有效资产投资组合的收益率模型,模型建立在可信性分布的基础上,而不是概率分布或可能性分布基础上.给出模糊环境下基于可信性分布的n种资产的最优投资组合问题的混合智能算法以寻找某种效用函数意义下的最优组合.并以实例仿真说明该方法的有效性.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

Mixed-integer minimax dynamic optimization for structure identification of glycerol metabolic network

Cell metabolism is a dynamic regulation process, in which its network structure and/or regulatory mechanisms can change constantly over time due to internal and external perturbations. This paper models glycerol metabolism in continuous fermentation as a nonlinear mixed-integer dynamic system by defining the time-varying metabolic network structure as an integer-valued function. To identify the dynamic network structure and kinetic parameters, we establish a mixed-integer minimax dynamic optimization problem with concentration robustness as its objective functional. By direct multiple shooting strategy and a decomposition approach consisting of convexification, relaxation and rounding strategy, the optimization problem is transformed into a large-scale approximate multistage parameter optimization problem. It is then solved using a competitive particle swarm optimization algorithm. We also show that the relaxation problem yields the best lower bound for the optimization problem, and its solution can be arbitrarily approximated by the solution obtained from rounding strategy. Numerical results indicate that the proposed mixed-integer dynamic system can better describe cellular self-regulation and response to intermediate metabolite inhibitions in continuous fermentation of glycerol. These numerical results show that the proposed numerical methods are effective in solving the large-scale mixed-integer dynamic optimization problems.     

A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem

Given a CNF (conjunctive normal form) Boolean expression with clauses of size at most two, the Max-2-SAT problem asks to find a truth assignment to the Boolean variables that makes true the maximum number of clauses. In this paper, we describe an innovative upper bound computation procedure which is centered around the use of equations and inequalities that are satisfied by all solutions to the problem. The procedure is incorporated in a branch-and-bound algorithm for Max-2-SAT. An initial solution to the problem is provided by an iterated tabu search heuristic. We present computational experience on the Max-2-SAT benchmark instances from the Max-SAT Evaluation 2007. The results show that the developed branch-and-bound algorithm is very competitive with the best previously reported techniques.     

Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem

This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path-following algorithm proposed by the authors for the LCP. If the LCP has a unique non-degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.Supported by Grant-in-Aids for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Young Scientists (63730014) and for General Scientific Research (63490010) of The Ministry of Education, Science and Culture.     

Linear programming for the 0–1 quadratic knapsack problem

In this paper we consider the quadratic knapsack problem which consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We propose a new method for computing an upper bound. This method is based on the solution of a continuous linear program constructed by adding to a classical linearization of the problem some constraints rebundant in 0–1 variables but nonredundant in continuous variables. The obtained upper bound is better than the bounds given by other known methods. We also propose an algorithm for computing a good feasible solution. This algorithm is an elaboration of the heuristic methods proposed by Chaillou, Hansen and Mahieu and by Gallo, Hammer and Simeone. The relative error between this feasible solution and the optimum solution is generally less than 1%. We show how these upper and lower bounds can be efficiently used to determine the values of some variables at the optimum. Finally we propose a branch-and-bound algorithm for solving the quadratic knapsack problem and report extensive computational tests.     

The maximum capture problem with random utilities: Problem formulation and algorithms

A model for the optimal location of new facilities in a competitive market is introduced under the hypothesis that customers' behavior can be modeled by random utility functions. It means that the company, that wished to locate, uses a random utility model to forecast the market share of a location. Therefore the company cannot forecast the behavior of every customer in a deterministic fashion, but is able to embed him by a probability distribution. Three formulations are proposed to compute upper bounds of the objective function and compared in a numerical simulation. A branch and bound method is developed and tested on examples with up to 50 potential locations, and a Variable Neighborhood Search heuristic is proposed to solve larger instances.     

圆形区域分散布局问题研究

针对圆形区域分散布局问题, 文中给出了一个带约束的非线性规划模型. 当布局点数量较少时, 通过将模型转化为无约束优化问题, 利用梯度方法进行求解; 对于布局点数量较多的情况, 提出了一个界为1/2的多项式时间的近似算法, 并进行了相应的算例分析, 进一步来验证算法解的合理性. 研究的结论及方法一定程度上丰富和完善了圆形区域的分散布局理论.     

New upper bounds for online strip packing

In this paper, we consider the online strip packing problem, in which a list of online rectangles has to be packed without overlap or rotation into one or more strips of width 1 and infinite height so as to minimize the required height of the packing. By analyzing a two-phase shelf algorithm, we derive a new upper bound 6.4786 on the competitive ratio for online one strip packing. This result improves the best known upper bound of 6.6623. We also extend this algorithm to online multiple strips packing and present some numeric upper bounds on their competitive ratios which are better than the previous bounds.     

Upper Bounds on Height of Terms in a Solution of a Semiunification Problem

In this paper, we investigate a decidable case of the term semiunification problem. In our case, the arity of any functional symbol in terms equals one (with a possible exception for outer symbols of terms, for which no restrictions are imposed). We propose an algorithm constructing the most general solution of the semiunification problem. In addition, we prove an upper bound on the height of this solution; this upper bound is linear with respect to heights of terms in the initial problem. Our method reduces the problem for terms to a special system of equations in free semigroups and solves the latter system. Bibliography: 10 titles.