Optimization and analysis of the profitability of tariff structures with two-part tariffs

Service providers often offer tariff structures with several two-part tariffs that consist of a fixed fee and a usage price, such that consumers may pick the tariff they prefer. Prices of tariffs have significant impacts on service providers’ profit, because they simultaneously influence consumers’ tariff choices and their usage. The number of tariffs also plays an important role, because more tariffs segment the market better but also increase the administrative burden and require more marketing effort. This article presents a mixed-integer nonlinear programming optimization problem to determine profit-maximizing tariffs; compares several heuristic search methods, in particular, the gradient method, stochastic search, and simulated annealing, to solve this problem; analyses the profitability of different tariff structures; and outlines the factors that drive differences in profitability across various tariff structures. The results show that especially for large samples of more than 100 consumers, simulated annealing performs best and deviates only 0.2% from the optimum. Structures with fewer two-part tariffs are generally sufficient, because additional two-part tariffs only negligibly increase service providers’ profit.     

How a dominant retailer might design a purchase contract for a newsvendor-type product with price-sensitive demand

A dominant retailer will purchase a newsvendor-type product from a manufacturer, who incurs a unit manufacturing cost k. The expected retail demand is a function of the unit retail price p. How should the retailer design her purchase contract? For this increasingly prevalent but inadequately studied scenario, we propose plausible adaptations of several contract formats that have been widely studied in the dominant-manufacturer context. For both symmetric-k and asymmetric-k-knowledge situations, we present performance results of these contracts. Our results then reveal that the performance of these contract formats under our scenario differs considerably from what one would surmise from the well-known results published for closely related scenarios. For example, the widely studied buyback and revenue-sharing formats turn out to be largely ineffective when implemented by a dominant retailer. In contrast, the two-part tariff format performs well relative to the theoretically optimal “menu of contracts.” Our results highlight the need to study purchase contract formats designed specifically for dominant-retailer newsvendor-product channels.     

Local search for the minimum label spanning tree problem with bounded color classes

In the Minimum Label Spanning Tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most r times in the input graph. This special case is polynomially solvable for r=2, and NP- and APX-complete for any fixed r?3.We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k=2 any local optimum yields an (r+1)/2-approximation of the global optimum, and that this bound is tight. For every k?3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

A fast approximation algorithm for the multicovering problem

The multicovering problem is: MIN cx subject to Ax≥b, xϵ{0, 1}ⁿ, where A is a matrix whose elements are all zero or one and b is a vector of positive integers. We present a fast heuristic for this important class of problems and analyze its worst-case performance: the ratio of the heuristic value to the optimum does not exceed the maximum row sum of the matrix A. The heuristic algorithm also provides a feasible dual solution vector that is useful in generating lower bounds on the value of the optimum.     

Optimum quantization and its applications

Minimum sums of moments or, equivalently, distortion of optimum quantizers play an important role in several branches of mathematics. Fejes Tóth's inequality for sums of moments in the plane and Zador's asymptotic formula for minimum distortion in Euclidean d-space are the first precise pertinent results in dimension d?2. In this article these results are generalized in the form of asymptotic formulae for minimum sums of moments, resp. distortion of optimum quantizers on Riemannian d-manifolds and normed d-spaces. In addition, we provide geometric and analytic information on the structure of optimum configurations. Our results are then used to obtain information on

(i)

the minimum distortion of high-resolution vector quantization and optimum quantizers,

(ii)

the error of best approximation of probability measures by discrete measures and support sets of best approximating discrete measures,

(iii)

the minimum error of numerical integration formulae for classes of Hölder continuous functions and optimum sets of nodes,

(iv)

best volume approximation of convex bodies by circumscribed convex polytopes and the form of best approximating polytopes, and

(v)

the minimum isoperimetric quotient of convex polytopes in Minkowski spaces and the form of the minimizing polytopes.

     

Properties of certain zero column-sum matrices with applications to the optimization of chemical reactors

This work is motivated by linear chemical reactor systems. The mathematical model of these systems employs a finite dimensional concentration vector which yields the properties of a discrete probability distribution. Central in the response of the system is a rate matrix. The properties of these matrices are analyzed in terms of the theories of Markoff and M-matrices. A linear objective function is selected and the optimization of a cascade system relative to changes of the sizes of the tanks is pursued. This amounts to the optimization of the objective function on R₊^m. The global optimum is shown to lie on the diagonal of the domain. Hence, the search for optimum can be simplified to a single dimension. Other related topics such as the effect of the number of tanks in the cascade on the optimum, conditions for off-diagonal stationary points and the constrained optimization are also considered.     

Optimum design of infinite journal bearing with a minimum of the friction moment

The isoperimetric problem (IP) of profiling the optimum outer shape of the gap of a closed hydrodynamic journal bearing of infinite length is formulated and solved in the incompressible “non-cavitating” fluid approximation. Whereas the maximum of the carrying capacity coefficient C_N is realized in the Rayleigh problem (RP), in the IP a minimum of the coefficient of the friction moment C_M on the neck (shaft) for given C_N is achieved. The structure of the optimum solution is established and it is shown that if C_N is less than the coefficient C_NR corresponding to the RP, the optimum gap height h is a continuous function of the polar angle θ. In the general case the optimum function h = h(θ) contains segments of four kinds. Two of them, h ≡ 1 and h ≡ H > 1, are boundary extremum segments (BES1) and BESH), which appear due to the fact that h has lower and upper bounds (h is measured relative to the minimum admissible height). The other two segments are two-sided extremum segments—TES. The first of these, TES1, is similar to the TES in Rayleigh's problem, in which h ≡ h₁ where 1 < h₁ < H. TES2 appears only in the IP For C_N > 0.75C_NK BES1 divides TES2 in two. The first part has a negative slope, and the second has a positive slope and connects BES1 with BESH or TES1. As C_N → C_NR the slopes of the tangents to TES2 approach ± ∞ and the segments themselves turn into two steps, i.e. into the well-known discontinuities of h in the RP Unlike the IP for a slider, the optimum gap of a journal bearing on TES2 can either be converging or diverging. Results of calculations are given to illustrate the theoretical analysis.     

Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

This paper considers the problem of finding a minimal triangulation of an undirected graph G = (V, E), where a triangulation is a set T such that every cycle in G = (V, E ∪ T) has a chord. A triangulation T is minimal (minimum) if no triangulation F exists such that F is a proper subset of $\text{T (¦F¦ < ¦T¦)}$, and an ordering α is optimal (optimum) if a minimal (minimum) triangulation is generated by α. A minimum triangulation (optimum ordering) is necessarily minimal (optimal), but the converse is not necessarily true. A necessary and sufficient condition for a triangulation to be minimal is presented. This leads to an algorithm for finding an optimal ordering α which produces a minimal set of “fill-in” when the process is viewed as triangular factorization of a sparse matrix.     

On the convergence of the MAOR method

In order to solve a linear system Ax = b, Hadjidimos et al. (1992) defined a class of modified AOR (MAOR) method, whose special case implies the MSOR method. In this paper, some sufficient and/or necessary conditions for convergence of the MAOR and MSOR methods will be achieved, when A is a two-cyclic matrix and when A is a Hermitian positive-definite matrix, an H-, L- or M-matrix, and a strictly or irreducibly diagonally dominant matrix. The convergence results on the MSOR method are better than some known theorems. The optimum parameters and the optimum spectral radii of the MAOR and MSOR methods are obtained, which also answers the open problem given by Hadjidimos et al.     

A distributed computation algorithm for solving portfolio problems with integer variables

A portfolio problem with integer variables can facilitate the use of complex models, including models containing discrete asset values, transaction costs, and logical constraints. This study proposes a distributed algorithm for solving a portfolio program to obtain a global optimum. For a portfolio problem with n integer variables, the objective function first is converted into an ellipse function containing n separated quadratic terms. Next, the problem is decomposed into m equal-size separable programming problems solvable by a distributed computation system composed of m personal computers linked via the Internet. The numerical examples illustrate that the proposed method can obtain the global optimum effectively for large scale portfolio problems involving integral variables.     

A variable neighborhood search based algorithm for finite-horizon Markov Decision Processes

This paper considers the application of a variable neighborhood search (VNS) algorithm for finite-horizon (H stages) Markov Decision Processes (MDPs), for the purpose of alleviating the “curse of dimensionality” phenomenon in searching for the global optimum. The main idea behind the VNSMDP algorithm is that, based on the result of the stage just considered, the search for the optimal solution (action) of state x in stage t is conducted systematically in variable neighborhood sets of the current action. Thus, the VNSMDP algorithm is capable of searching for the optimum within some subsets of the action space, rather than over the whole action set. Analysis on complexity and convergence attributes of the VNSMDP algorithm are conducted in the paper. It is shown by theoretical and computational analysis that, the VNSMDP algorithm succeeds in searching for the global optimum in an efficient way.     

Optimum split trees

A split tree is a special kind of a binary search tree introduced by B. A. Sheil (Comm. ACM21 (1978), 947–958). He conjectured that constructing an optimum split tree is an intractable problem since there is a difficulty in applying the dynamic programming technique. It is realized that the difficulty arises since top down decisions are required while applying the bottom up dynamic programming technique. It is demonstrated that it is possible in this case to overcome such a difficulty, and a polynomial algorithm for constructing an optimum split tree is presented. This algorithm incorporates top down decisions into a dynamic programming procedure similar to D. E. Knuth's (Acta Inform. 1 (1971), 14–25) algorithm for constructing an optimum binary search tree. The probabilities of unsuccessful searches are taken into account. A modification for the case that equiprobable keys are permitted is discussed.     

The isoperimetric problem of profiling of the optimum clearance of an infinite plane slider bearing

The isoperimetric problem (IP) of profiling the optimum clearance between a plane support surface and an infinite cylindrical (plane) slide is formulated and solved in the incompressible fluid approximation. If the maximum of the carrying capacity coefficient C_N is realized in the well-known Rayleigh problem (RP), where L in the IP the minimum friction is ensured for the given value of C_N. The structure of the optimum solution is explained and it is established that if C_N is less than the coefficient C_NR corresponding to the RP, then the clearance height h is a continuous function of the x coordinate measured along the support surface. In the general case the optimum function h = h(x) may contain segments of four kinds. Two of them, h = 1 and h = H > 1, are the boundary extremum segments (BEST and BESH), which appear due to the fact that h has upper and lower bounds. The other two segments are bilateral extremum segments. TESL is similar to the TES in Rayleigh's problem, in which h = h₁, where 1 < h₁ < H. TES2 appears only in the IE It has a negative slope and connects BEST with BESH or TESL. As C_N → C_NR the slope of TES2 approaches minus infinity, and the segment itself turns into a step, i.e. into the well-known discontinuity of h in the RP.     

A new solution algorithm for improving performance of ant colony optimization

This study proposes an improved solution algorithm using ant colony optimization (ACO) for finding global optimum for any given test functions. The procedure of the ACO algorithms simulates the decision-making processes of ant colonies as they forage for food and is similar to other artificial intelligent techniques such as Tabu search, Simulated Annealing and Genetic Algorithms. ACO algorithms can be used as a tool for optimizing continuous and discrete mathematical functions. The proposed algorithm is based on each ant searches only around the best solution of the previous iteration with β. The proposed algorithm is called as ACORSES, an abbreviation of ACO Reduced SEarch Space. β is proposed for improving ACO’s solution performance to reach global optimum fairly quickly. The ACORSES is tested on fourteen mathematical test functions taken from literature and encouraging results were obtained. The performance of ACORSES is compared with other optimization methods. The results showed that the ACORSES performs better than other optimization algorithms, available in literature in terms of minimum values of objective functions and number of iterations.     

Project selection with discounted returns and multiple constraints

This paper considers the problem of selecting a subset of N projects subject to multiple resource constraints. The objective is to maximize the net present value of the total return, where the return from each project depends on its completion time and the previously implemented projects. It is observed that the optimal order (sequence) of projects does not depend on the particular subset of selected projects and hence the overall problem reduces to a multiconstraint nonlinear integer (0–1) problem. This problem can be solved optimally in pseudo-polynomial time using a dynamic programming method but the method is impractical except when the number of constraints, K, is very small. We therefore propose two heuristic methods which require O(N³K) and O(N⁴K) computations, respectively, and evaluate them computationally on 640 problems with up to 100 projects and up to 8 constraints. The results show that the best heuristic is on the average within 0.08% of the optimum for the single-constraint case and within 2.61% of the optimum for the multiconstraint case.     

Optimum Lot-Size Policy if Tools Break Down Frequently

A well-known formula gives the optimum length of a production series by balancing change-over costs against inventory costs. This formula can no longer be considered as optimum in the case of a high breakdown rate of the tools. We can often reduce our costs in such situations by ending the production series when a breakdown occurs. This introduces a variability in the lot-sizes, which in turn causes higher stock levels.A production policy was developed, based on two limits, Q_l and Q₂. Production is stopped either at the first break-down after Q₁ units have been produced, or at Q₂. Optimum values of Q₁ and Q₂ were derived and can be read off from a set of graphs.One assumption of this theory is that tools are always available, which theoretically requires an infinite stock of these tools.A Monte Carlo programme was set up to study the situation, in which the number of tools was limited. The number of tools, and the reorder-level for the products, required for a desired probability of stock-out, can be derived by the programme.The theoretical values of Q₁ and Q₂ could be considered optimum for practical purposes in the cases under consideration.     

Benders's method revisited

The master problem in Benders's partitioning method is an integer program with a very large number of constraints, each of which is usually generated by solving the integer program with the constraints generated earlier. Computational experience shows that the subset B of those constraints of the master problem that are satisfied with equality at the linear programming optimum often play a crucial role in determining the integer optimum, in the sense that only a few of the remaining inequalities are needed. We characterize this subset B of inequalities. If an optimal basic solution to the linear program is nondegenerate in the continuous variables and has p integer-constrained basic variables, then the corresponding set B contains at most 2^p inequalities, none of which is implied by the others. We give an efficient procedure for generating an appropriate subset of the inequalities in B, which leads to a considerably improved version of Benders's method.     

Dynamic pricing of electricity in retail markets

This paper aims at defining a dynamic and flexible tariff structure for a distribution company that protects the retail consumers against the excessive fluctuations of the wholesales market prices. We propose a two-stage pricing scheme that sets in a first-stage a time-of-use tariff that is corrected later by a dynamic component once the real-time demand has been observed. A personalized tariff scheme may be offered by a distribution company to each dynamic customer by allowing him to choose the appropriate robustness level expressed in terms of variability between the first and the second-stage decisions. The arising limited recourse model has been tested on realistic test problems, by using a slight modification of a recently proposed interior point solution framework.      

Dynamic huffman coding

This note shows how to maintain a prefix code that remains optimum as the weights change. A Huffman tree with nonnegative integer weights can be represented in such a way that any weight w at level l can be increased or decreased by unity in O(l) steps, preserving minimality of the weighted path length. One-pass algorithms for file compression can be based on such a representation.