Concave minimization via conical partitions and polyhedral outer approximation

An algorithm is proposed for globally minimizing a concave function over a compact convex set. This algorithm combines typical branch-and-bound elements like partitioning, bounding and deletion with suitably introduced cuts in such a way that the computationally most expensive subroutines of previous methods are avoided. In each step, essentially only few linear programming problems have to be solved. Some preliminary computational results are reported.Parts of the present paper were accomplished while the author was on leave at the University of Florida.Parts of the present paper were completed while the author was on leave at the University of Trier as a fellow of the Alexander von Humboldt foundation.     

Network cost minimization using threshold-based discounting

A network design problem in which every pair of nodes can communicate directly is discussed. However, there is an incentive to combine flow from different sources, namely, if the total flow through a link exceeds the prescribed threshold, then the cost of this flow is discounted by a factor α. Alternative mixed integer linear formulations for this problem are presented. Computational results comparing the models on a set of benchmark problems are also presented. The results show the effectiveness of the formulations: for discounts of 5–10%, the gaps between linear and integer solutions are within few percent. Such a model offers economic incentives in building and utilizing communication networks.     

The multiple container loading cost minimization problem

In the shipping and transportation industry, there are several types of standard containers with different dimensions and different associated costs. In this paper, we examine the multiple container loading cost minimization problem (MCLCMP), where the objective is to load products of various types into containers of various sizes so as to minimize the total cost. We transform the MCLCMP into an extended set cover problem that is formulated using linear integer programming and solve it with a heuristic to generate columns. Experiments on standard bin-packing instances show our approach is superior to prior approaches. Additionally, since the optimal solutions for existing test data is unknown, we propose a technique to generate test data with known optimal solutions for MCLCMP.     

On the weighting of the mean-absolute-deviation cost minimization model

The mean-absolute-deviation cost minimization model, which aims to minimize sum of the mean value and the absolute deviation (AD) of the total cost multiplied by a given non-negative weighting, is one of a number of typical robust optimization models. This paper first uses a straightforward example to show that the solution obtained by this model with some weightings is not actually an optimal decision. This example also illustrates that the mean-absolute-deviation cost minimization model cannot be regarded as the conventional weighted transformation of the relevant multiobjective minimization model aiming to simultaneously minimize the mean value and AD. This paper further proves that the optimal solution obtained by the mean-absolute-deviation cost minimization model with the weighting not exceeding 0.5 will not be absolutely dominated by any other solution. This tight upper bound provides a useful guideline for practical applications.     

Applying cost minimization techniques to hospitals: A comment

In a challenging paper, [Suthummanon S., Omachonu V.K., 2007. Cost minimization models: Applications in a teaching hospital. European Journal of Operational Research 186, 1175–1183] (hereafter SO), present an interesting cost minimization model to be applied to improve hospital efficiency. Though the technical aspects of the statistical analysis SO present cannot be criticized, it is argued that the application to hospital costs the authors present is fraught with conceptual and practical problems. These need to be resolved before a length of stay approach to minimizing hospital costs can have any practical relevance.     

Randomized heuristics for handover minimization in mobility networks

A mobile device connects to the cell tower (base station) from which it receives the strongest signal. As the device moves it may connect to a series of towers. The process in which the device changes the base station it is connected to is called handover. A cell tower is connected to a radio network controller (RNC) which controls many of its operations, including handover. Each cell tower handles an amount of traffic and each radio network controller has capacity to handle a maximum amount of traffic from all base stations connected to it. Handovers between base stations connected to different RNCs tend to fail more often than handovers between base stations connected to the same RNC. Handover failures result in dropped connections and therefore should be minimized. The Handover Minimization Problem is to assign towers to RNCs such that RNC capacity is not violated and the number of handovers between base stations connected to different RNCs is minimized. We describe an integer programming formulation for the handover minimization problem and show that state-of-the-art integer programming solvers can solve only very small instances of the problem. We propose several randomized heuristics for finding approximate solutions of this problem, including a GRASP with path-relinking for the generalized quadratic assignment problem, a GRASP with evolutionary path-relinking, and a biased random-key genetic algorithm. Computational results are presented.     

Concave minimum cost network flow problems solved with a colony of ants

In this work we address the Single-Source Uncapacitated Minimum Cost Network Flow Problem with concave cost functions. This problem is NP-Hard, therefore we propose a hybrid heuristic to solve it. Our goal is not only to apply an ant colony optimization (ACO) algorithm to such a problem, but also to provide an insight on the behaviour of the parameters in the performance of the algorithm. The performance of the ACO algorithm is improved with the hybridization of a local search (LS) procedure. The core ACO procedure is used to mainly deal with the exploration of the search space, while the LS is incorporated to further cope with the exploitation of the best solutions found. The method we have developed has proven to be very efficient while solving both small and large size problem instances. The problems we have used to test the algorithm were previously solved by other authors using other population based heuristics. Our algorithm was able to improve upon some of their results in terms of solution quality, proving that the HACO algorithm is a very good alternative approach to solve these problems. In addition, our algorithm is substantially faster at achieving these improved solutions. Furthermore, the magnitude of the reduction of the computational requirements grows with problem size.     

Efficient visit frequencies for polling tables: minimization of waiting cost

Polling systems have been used as a central model for the modeling and analysis of many communication systems. Examples include the Token Ring network and a communications switch. The common property of these systems is the need to efficiently share a single resource (server) amongN entities (stations). In spite of the massive research effort in this area, very little work has been devoted to the issue of how toefficiently operate these systems.In the present paper we deal with this problem, namely with how to efficiently allocate the server's attention among theN stations. We consider a framework in which a predetermined fixed visit order (polling table) is used to establish the order by which the server visits the stations, and we address the problem of how to construct an efficient (optimal) polling table. In selecting a polling table the objective is to minimize the mean waiting cost of the system, a weighted sum of the mean delays with arbitrary cost parameters. Since the optimization problem involved is very hard, we use an approximate approach. Using two independent analyses, based on a lower bound and on mean delay approximations, we derive very simple rules for the determination of efficient polling tables. The two rules are very similar and even coincide in most cases. Extensive numerical examination shows that the rules perform well and that in most cases the system operates very close to its optimal operation point.     

Minimum cost multiflows in undirected networks

LetN = (G, T, c, a) be a network, whereG is an undirected graph,T is a distinguished subset of its vertices (calledterminals), and each edgee ofG has nonnegative integer-valuedcapacity c(e) andcost a(e). Theminimum cost maximum multi(commodity)flow problem (*) studied in this paper is to find ac-admissible multiflowf inG such that: (i)f is allowed to contain partial flows connecting any pairs of terminals, (ii) the total value off is as large as possible, and (iii) the total cost off is as small as possible, subject to (ii). This generalizes, on one hand, the undirected version of the classical minimum cost maximum flow problem (when |T| = 2), and, on the other hand, the problem of finding a maximum fractional packing ofT-paths (whena 0). Lovász and Cherkassky independently proved that the latter has a half-integral optimal solution.A pseudo-polynomial algorithm for solving (*) has been developed earlier and, as its consequence, the theorem on the existence of a half-integral optimal solution for (*) was obtained. In the present paper we give a direct, shorter, proof of this theorem. Then we prove the existence of a half-integral optimal solution for the dual problem. Finally, we show that half-integral optimal primal and dual solutions can be designed by a combinatorial strongly polynomial algorithm, provided that some optimal dual solution is known (the latter can be found, in strongly polynomial time, by use of a version of the ellipsoid method).This work was partially supported by Chaire municipale, Mairie de Grenoble, France.     

Minimum cost flow algorithms for series-parallel networks

It is shown that an acyclic multigraph with a single source and a single sink is series-parallel if and only if for arbitrary linear cost functions and arbitrary capacities the corresponding minumum cost flow problem can be solved by a greedy algorithm. Furthermore, for networks of this type with m edges and n vertices, two O(mn+logm)-algorithms. One of them is based on the greedy scheme.     

A cost minimization procedure for mixed model production lines with normally distributed task times

This paper presents design procedures for mixed model production lines. The design objective is to minimize the total operating cost, composed of labor cost, in-process inventory cost, and set-up cost. This paper is an extension of our previous work in which we recognize the variability associated with task times and propose a procedure that can handle either deterministic or stochastic task times.     

A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem

In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.     

关于凹函数性质的探讨

从凹函数的一个问题出发,给出了该问题的反例以及问题结论成立的充要条件和充分条件.     

On Concave Operators

We prove that a u0-concave operator can include other concave operators, and derive a sufficient and necessary condition for the existence and uniqueness of the fixed point of a kind of u0-concave operator under a weaker condition.     

Supply chain network operations management of a blood banking system with cost and risk minimization

Blood service operations are a key component of the healthcare system all over the world and yet the modeling and the analysis of such systems from a complete supply chain network optimization perspective have been lacking due to their associated unique challenges. In this paper, we develop a generalized network optimization model for the complex supply chain of human blood, which is a life-saving, perishable product. In particular, we consider a regionalized blood banking system consisting of collection sites, testing and processing facilities, storage facilities, distribution centers, as well as points of demand, which, typically, include hospitals. Our multicriteria system-optimization approach on generalized networks with arc multipliers captures many of the critical issues associated with blood supply chains such as the determination of the optimal allocations, and the induced supply-side risk, as well as the induced cost of discarding the waste, while satisfying the uncertain demands as closely as possible. The framework that we present is also applicable, with appropriate modifications, to the optimization of other supply chains of perishable products.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

Least cost influence propagation in (social) networks

Influence maximization problems aim to identify key players in (social) networks and are typically motivated from viral marketing. In this work, we introduce and study the Generalized Least Cost Influence Problem (GLCIP) that generalizes many previously considered problem variants and allows to overcome some of their limitations. A formulation that is based on the concept of activation functions is proposed together with strengthening inequalities. Exact and heuristic solution methods are developed and compared for the new problem. Our computational results also show that our approaches outperform the state-of-the-art on relevant, special cases of the GLCIP.     

The role of repair strategy in warranty cost minimization: An investigation via quasi-renewal processes

Most companies seek efficient rectification strategies to keep their warranty related costs under control. This study develops and investigates different repair strategies for one- and two-dimensional warranties with the objective of minimizing manufacturer’s expected warranty cost. Static, improved and dynamic repair strategies are proposed and analyzed under different warranty structures. Numerical experimentation with representative cost functions indicates that performance of the policies depend on various factors such as product reliability, structure of the cost function and type of the warranty contract.