A branch-and-bound algorithm for the concave cost supply problem

Effective supplier selection and allocation of order quantity among multiple suppliers are indispensable to the success of a manufacturing company. While companies have begun to turn into a comprehensive multi-criteria approach, most buyers still consider purchasing cost to be their primary concern in selecting their suppliers. In this paper, we consider the concave cost supply problem where a manufacturer seeks to select the suppliers and simultaneously procure the quantity of material/component required for production at the minimum total cost during a standard production period. We provide and validate an effective and efficient branch-and-bound algorithm that is finite and that finds the global optimal solution of the problem without any restrictions on the cost functions or on the set of input parameters used in the problem. Numerical experiments are conducted to evaluate the performance of the proposed algorithm.     

Capacitated multicommodity network flow problems with piecewise linear concave costs

Lagrangian techniques have been commonly used to solve the capacitated multi-commodity network flow problem with piecewise linear concave costs. In this paper, we show that the resulting lower bounds are no better than those obtained by the linear programming relaxation and focus on developing algorithms based on the latter. For that purpose, we characterize structural properties of the optimal solution of the linear programming relaxation and propose a heuristic solution approach that uses these properties to transform the fractional solution into an integer one. Our computational experiments show the effectiveness of the algorithm.     

An ant colony system-based hybrid algorithm for square root concave cost transhipment problems

Concave cost transhipment problems are difficult to optimally solve for large-scale problems within a limited period of time. Recently, some modern meta-heuristics have been employed for the development of advanced local search based or population-based stochastic search algorithms that can improve the conventional heuristics. Besides these meta-heuristics, the ant colony system algorithm is a population-based stochastic search algorithm which has been used to obtain good results in many applications. This study employs the ant colony system algorithm, coupled with some genetic algorithm and threshold accepting algorithm techniques, to develop a population based stochastic search algorithm for efficiently solving square root concave cost transhipment problems. The developed algorithms are evaluated with a number of problem instances. The results indicate that the proposed algorithm is more effective for solving square root concave cost transhipment problems than other recently designed local search based algorithms and genetic algorithm.     

Concave programming and piece-wise linear programming

This paper discusses the mathematical foundations of a technique that has been used extensively in structural optimization.^1–6 Two basic problems are considered. The first of these is the concave programming problem which consists of finding the global minimum of ‘piece-wise concave functions’ on ‘piece-wise concave sets’. Since any function can be approximated by a piece-wise concave function, this method could in principle be used to find the global minimum in non-convex optimization problems. The second one is the piece-wise linear programming problem in which the objective function is convex and piece-wise linear. The iterative method outlined for handling this problem is shown to be much more efficient than the standard simplex method of linear programming.     

On the global minimization of concave functions

Summary Many important classes of decision models give rise to the problem of finding a global minimum of a concave function over a convex set. Since many local minima can occur, concave minimization belongs to the hard global optimization problems, where standard nonlinear programming procedures fail.After a brief survey on important classes of decision models that can be formulated as concave minimization problems, the two main solution approaches are discussed: branch-and-bound combined with convex underestimation and outer approximation by cutting planes.

---

Zusammenfassung Eine Reihe wichtiger Klassen von Entscheidungsmodellen führt auf die globale Minimierung konkaver Funktionen über konvexen Mengen. Da viele lokale Minima auftreten können, ist die konkave Minimierung zu den harten globalen Optimierungsaufgaben zu rechnen, bei denen Standardverfahren der nichtlinearen Optimierung nicht zum Ziel führen.Nach einer kurzen Übersicht über wichtige Klassen von Entscheidungsmodellen, die sich als konkave Minimierungsprobleme formulieren lassen, werden die beiden wichtigsten Lösungsansätze diskutiert: Eine Kombination von Branch und Bound mit konvexer Approximation und äußere Approximationsverfahren mit Hilfe von Schnittebenen.

     

Enumerative techniques for solving some nonconvex global optimization problems

Summary We give an overview on different methods for solving nonconvex minimization problems using techniques of enumeration of extreme points. The problems considered include concave, indefinite quadratic, and special structured problems such as the concave cost network flow problem and linear complementarity. For methods that enumerate the extreme points according to the ascending order of the value of a linear underestimating function we propose new techniques for obtaining such underestimators.

---

Zusammenfassung Wir geben einen Überblick über verschiedene Methoden für nicht konvexe Minimisierungsaufgaben. Insbesondere diskutieren wir Aufzählungsmethoden für Extrempunkte. Wir betrachten konkave, quadratisch indefinite Probleme ebenso wie Probleme spezieller Struktur: konkave Netzwerk-Fluß-Probleme und lineare Komplementaritäts-Probleme. Wir schlagen neue Methoden vor, um lineare untere Schranken für Aufzählungstechnicken zu erhalten.

     

浮动凹弧底推杆-盘形凸轮组合机构的运动保真性研究

 浮动凹弧底推杆-盘形凸轮组合机构的Ⅰ类综合问题即是其综合理论的重要内容,又是其工程推广应用的重要准备.然而,机构的Ⅰ类综合问题是一个十分复杂的问题,难以一次性解决.“运动保真条件”是Ⅰ类综合问题必须首先保证的重要前提性条件.将“支撑函数法”应用于浮动凹弧底推杆-盘形凸轮组合机构,成功解决了预设凸轮轴心O₁（x_O1,y_O1）条件下,凸轮曲率半径的通用公式和“运动保真条件”.在为未来解决该类机构Ⅰ类综合问题奠定重要前提基础同时,还将“支撑函数法”推广拓展为适用于新型组合机构的一种通用有效方法.     

Optimizing Aircraft Routings in response to Groundings and Delays

This paper presents the time-band optimization model for reconstructing aircraft routings in response to groundings and delays experienced over the course of the day. Whenever the schedule is disrupted, the immediate objective of the airlines is to minimize the cost of reassigning aircraft to flights taking into account available resources and other system constraints. Associated costs are measured by flight delays and cancellations. The time-band model is constructed by transforming the routing problem into a time-based network in which the time horizon is discretized. The resulting formulation is an integral minimum cost network flow problem with side constraints. Conditions for which an exact solution to the model represents an optimal solution for the original problem are stated. The transformation procedure is polynomial with respect to the number of airports and flights in the schedule. Computational experience shows that the underlying network structure of the transformed problem often leads to integral solutions when solved with a standard linear programming code. Empirical results using Continental Airline data demonstrate that the solutions obtained are either provably optimal or no more than a few percentage points from the lower bound.     

Optimized superstationary anastigmatic mounts of concave gratings

Two subfamilies of concave grating superstationary anastigmatic mounts that provide minimum chromatic aberrations are described. The obtained approximate formulas can be used to design flat-field spectrographs and multi/demultiplexers for optical communication networks. Two specific mounts and their performance are presented.     

$M$ 矩阵的线性互补问题的误差界

研究了线性互补问题的误差界。首先，利用主对角部分为单位矩阵的 $M$ 矩阵的一个函数，给出该类线性互补问题的误差界理论。之后，通过线性互补问题的模型转化，将误差界理论进行推广，给出系数矩阵为一般 $M$ 矩阵的线性互补问题的误差界。用低阶和高阶的例子对误差界理论进行了验证和比较。数值结果表明，提出的误差界理论是有效的和实用的。     

Experiments with hybrid Bernstein global optimization algorithm for the OPF problem in power systems

This article presents an algorithm based on the Bernstein form of polynomials for solving the optimal power flow (OPF) problem in electrical power networks. The proposed algorithm combines local and global optimization methods and is therefore referred to as a ‘hybrid’ Bernstein algorithm in the context of this work. The proposed algorithm is a branch-and-bound procedure wherein a local search method is used to obtain a good upper bound on the global minimum at each branching node. Subsequently, the Bernstein form of polynomials is used to obtain a lower bound on the global minimum. The performance of the proposed algorithm is compared with the previously reported Bernstein algorithm to demonstrate its efficacy in terms of the chosen performance metrics. Furthermore, the proposed algorithm is tested on the OPF problem for several benchmark IEEE power system examples and its performance is compared with generic global optimization solvers such as BARON and COUENNE. The test results demonstrate that the hybrid Bernstein global optimization algorithm delivers satisfactory performance in terms of solution optimality.     

A SINGULAR-ARC APPROXIMATION TO A DYNAMIC SAILPLANE FLIGHT PATH OPTIMIZATION PROBLEM

A dynamic sailplane performance problem is investigated using optimal control theory. The problem is to minimize the total flight time between successive thermals subject to zero altitude loss. From the original nonlinear optimal control problem, a singular linear/quadratic problem is derived and solved.

A relationship between the original optimal control problem and a certain parameter optimization problem is explored, and it is shown that the solution to this parameter optimization provides a lower bound for the minimum flight time of the original optimal control problem. The parameter optimization solution is adopted as the reference trajectory for the linear/quadratic problem. Finally, the linear/quadratic problem is shown to provide a good approximation to the original optimal control problem at a small fraction of the computing cost.     

Optical demultiplexer using a silicon concave diffraction grating

A demultiplexer composed of a concave diffraction grating and a multimode slab waveguide is attractive since it has many advantageous features. However, this type of demultiplexer has had high demultiplexing losses until now, because the concave diffraction gratings used had poor diffraction efficiency. A silicon concave diffraction grating has been developed to overcome this problem, manufactured by cylindrically bending a thin silicon plane diffraction grating. The diffraction efficiency of this grating was 82% at a blaze wavelength. The five-channel demultiplexer was assembled with this grating as well as with a multimode slab waveguide and a fiber array. Its branching loss was in the 1.4-1.8-dB range.     

A COMPUTATIONAL STUDY OF EMPIRICAL DECISION HORIZONS IN INFINITE HORIZON, MULTIPERIOD NETWORK FLOW PROBLEMS

The minimum cost, multiperiod network flow model is an important optimization model for solving problems in many application areas including resource scheduling, planning and distribution. This network model describes decision making problems over time. In earlier work, we discussed the development, implementation and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method exploits the natural decomposition of multiperiod network problems, by limiting its pivoting activity to the date of the last few time periods. Both the solution CPU time and pivot count are linear in the number of time periods. For standard network optimization codes, the pivot count is linear while the solution time is approximately quadratic in the number of periods.

Here we present a computational study of the natural decomposition of, or empirical decision horizons for, an “infinite” horizon, multiperiod network model. We demonstrate the existence of such horizons for a model for which there is no guarantee of having an exact, or theoretical, decision horizon. When a problem having a sufficiently large number of time periods is solved, there is no effect on the decisions to be made for the first few time periods. Thus, the early periods' solution to a problem having an infinite number of time periods may be considered solved.     

An optimal procedure for solving the hierarchical network design problem

The hierarchical network design problem consists of finding a minimum cost bilevel network that connects all the nodes in a set, created by a loopless main path and a forest. The main path is formed by primary (higher cost) arcs, providing a path between an origin node and a destination node. The forest, built using secondary (lower cost) arcs, connects all the nodes not on the main path, to the path itself. We state and prove some properties of the problem, which allow finding good upper bounds to the solution in polynomial time when the primary costs are proportional to secondary costs. We also propose an O(n⁴) procedure to improve on these bounds. In turn, these bounds are used to significantly reduce the number of nodes and arcs of the problem. Once the problem is reduced, large instances can be solved to optimality. At this stage, we use one of two linear integer optimization formulations. The first and preferred one is based on multicommodity flows, which avoids the formation of subtours. The second formulation avoids subtours by iteratively adding ad hoc constraints. We show some examples and provide computational experiments performed on networks with sizes up to 600 nodes and 14 000 arcs.     

All-sky camera with a concave mirror

The characteristics of an all-sky camera with a concave mirror are analyzed. A differential equation for a concave aspheric mirror with constant angular magnification is derived for the general dependence of the camera image height on the camera field angle. This equation is solved in parametric form for the case of a concave mirror with a constant angular magnification. The explicit equations for the shape of the aspheric mirror are given for some particular values of the angular magnification. Parametric equations of the surface shape for sevenfold angular magnification are developed into a power series that is used to analyze the imaging performance of such a mirror. The performance of the concave aspheric mirror is compared with that of a spherical mirror. The minimal camera-to-mirror distance is determined as a function of the blur allowed and the camera lens aperture. Some characteristics of convex mirrors are also presented for comparison.     

A class of solution-invariant transformations of cost functions for minimum cost flow phase unwrapping

Phase unwrapping (PU) represents an important step in synthetic aperture radar interferometry (InSAR) and other interferometric applications. Among the different PU methods, the so called branch-cut approaches play an important role. In 1996 M. Costantini [Proceedings of the Fringe '96 Workshop ERS SAR Interferometry (European Space Agency, Munich, 1996), pp. 261-272] proposed to transform the problem of correctly placing branch cuts into a minimum cost flow (MCF) problem. The crucial point of this new approach is to generate cost functions that represent the a priori knowledge necessary for PU. Since cost functions are derived from measured data, they are random variables. This leads to the question of MCF solution stability: How much can the cost functions be varied without changing the cheapest flow that represents the correct branch cuts? This question is partially answered: The existence of a whole linear subspace in the space of cost functions is shown; this subspace contains all cost differences by which a cost function can be changed without changing the cost difference between any two flows that are discharging any residue configuration. These cost differences are called strictly stable cost differences. For quadrangular nonclosed networks (the most important type of MCF networks for interferometric purposes) a complete classification of strictly stable cost differences is presented. Further, the role of the well-known class of node potentials in the framework of strictly stable cost differences is investigated, and information on the vector-space structure representing the MCF environment is provided.     

MULTI-PERIOD STOCHASTIC NETWORK FLOW PROBLEMS WITH SERVICE LEVEL REQUIREMENTS: APPROXIMATION AND ERROR ESTIMATES

A multi-period network flow formulation with uncertain demands is proposed which covers many stochastic production and inventory models with service level requirements. The problem is approximated with a concave cost deterministic network flow problem. Relative error bounds are given which indicate that the approximation is good enough to be accepted in practice.     

Optimal design of hybrid laminates with discrete ply angles for maximum buckling load and minimum cost

The design of hybrid symmetric laminated plates consisting of high-stiffness surface and low-stiffness core layers is presented. In the first problem the maximization of buckling load is carried out over a discrete set of ply angles. In the second problem the minimum number of high-stiffness plies is determined for a given buckling load to minimize the material cost. Boolean variables are introduced to specify stacking sequence. Solution of the linear optimization problem yields an optimal stacking sequence. The effect of hybridization is investigated for various problem parameters such as the aspect ratio of the laminate and the number of plies. The optimal designs are obtained with upper bound constraints on the effect of bending-twisting coupling stiffnesses. Results are given for hybrid graphite-epoxy/glass-epoxy laminates under both uniaxial and biaxial loadings.     

Solving the minimum flow problem with interval bounds and flows

The minimum cost flow problem with interval data can be solved using two minimum cost flow problems with crisp data. In this paper, the idea of Ghiyasvand was extended for solving the minimum flow problem with interval-valued lower, upper bounds and flows. This problem can be solved using two minimum flow problems with crisp data. Then, this result is extended to networks with fuzzy lower, upper bounds and flows.