Pricing and revenue maximization over a multicommodity transportation network: the nonlinear demand case

This paper is concerned with the design of efficient exact and heuristic algorithms for addressing a bilevel network pricing problem where demand is a nonlinear function of travel cost. The exact method is based on the piecewise linear approximation of the demand function, yielding mixed integer programming formulations, while heuristic procedures are developed within a bilevel trust region framework.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

Dynamic pricing and scheduling in a multi-class single-server queueing system

This paper investigates an optimal sequencing and dynamic pricing problem for a two-class queueing system. Using a Markov Decision Process based model, we obtain structural characterizations of optimal policies. In particular, it is shown that the optimal pricing policy depends on the entire queue length vector but some monotonicity results prevail as the composition of this vector changes. A numerical study finds that static pricing policies may have significant suboptimality but simple dynamic pricing policies perform well in most situations.     

Heuristic Methods for the Multi-product Dynamic Lot Size Problem

Many heuristics exist for the single-item dynamic lot-size problem, for example, the Silver-Meal, the part period balancing and a simple variant of the part period balancing. The worst case performances of these heuristics have been shown to be zero, 1/3 and 1/2 respectively. These heuristics can be generalized to the dynamic version of the joint replenishment problem, that is, the multi-product dynamic lot-size problem. Such a generalization of the Silver-Meal heuristic has been shown to perform well on a set of test problems. This paper generalizes the part period balancing heuristic, and a simple variant of it to the multiproduct dynamic lot-size problem, and shows that the worst case performances of the generalized heuristics remain 1/3 and 1/2 respectively. An improved version of the generalized Silver-Meal heuristic is also given.     

Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15 minutes. In two of the three instances, the optimal solution is found within this time frame.     

Robust portfolio optimization with a hybrid heuristic algorithm

Estimation errors in both the expected returns and the covariance matrix hamper the construction of reliable portfolios within the Markowitz framework. Robust techniques that incorporate the uncertainty about the unknown parameters are suggested in the literature. We propose a modification as well as an extension of such a technique and compare both with another robust approach. In order to eliminate oversimplifications of Markowitz’ portfolio theory, we generalize the optimization framework to better emulate a more realistic investment environment. Because the adjusted optimization problem is no longer solvable with standard algorithms, we employ a hybrid heuristic to tackle this problem. Our empirical analysis is conducted with a moving time window for returns of the German stock index DAX100. The results of all three robust approaches yield more stable portfolio compositions than those of the original Markowitz framework. Moreover, the out-of-sample risk of the robust approaches is lower and less volatile while their returns are not necessarily smaller.     

Simple heuristics for the assembly line worker assignment and balancing problem

We propose simple heuristics for the assembly line worker assignment and balancing problem. This problem typically occurs in assembly lines in sheltered work centers for the disabled. Different from the well-known simple assembly line balancing problem, the task execution times vary according to the assigned worker. We develop a constructive heuristic framework based on task and worker priority rules defining the order in which the tasks and workers should be assigned to the workstations. We present a number of such rules and compare their performance across three possible uses: as a stand-alone method, as an initial solution generator for meta-heuristics, and as a decoder for a hybrid genetic algorithm. Our results show that the heuristics are fast, they obtain good results as a stand-alone method and are efficient when used as a initial solution generator or as a solution decoder within more elaborate approaches.     

The impact of dynamic pricing on the economic order decision

This paper analyzes the impact of dynamic pricing on the single product economic order decision of a monopolist retailer. Items are procured from an external supplier according to the economic order quantity (EOQ) model and are sold to customers on a single market without competition following the simple monopolist pricing problem. Coordinated decision making of optimal pricing and ordering is influenced by operating costs – including ordering and inventory holding costs – and the demand rate obtained from a price response function. The retailer is allowed to vary the selling price, either in a fixed number of discrete points in time or continuously. While constant and continuous pricing have received much attention in the literature, problems with a limited number of price changes are rather rare. This paper illustrates the benefit of dynamically changing prices to achieve operational efficiency in the EOQ model, that is to trigger high demand rates when inventories are high. We provide structural properties of the optimal time instants when the price should be changed. Taking into account costs for changes in price, it provides numerical guidance on number, timing, and size of price changes during an order cycle. Numerical examples show that the benefits of dynamic pricing in an EOQ framework can be achieved with only a few price changes and that products being unprofitable under static pricing may become profitable under dynamic pricing.     

Another heuristic for minimizing total average cycle stock subject to practical constraints

This paper considers the setting of reorder intervals of a population of items for minimizing the total average cycle stock subject to a limit on the total number of replenishments per unit time, and a restricted set of possible intervals. Silver and Moon have investigated the problem with the use of dynamic programming, and they also proposed a heuristic for solving it. This paper presents a new 0-1 linear programming approach to the problem. Based upon the solution of the relaxed 0-1 linear programming formulation, a simple heuristic is proposed to solve the reorder problem. Limited numerical results using realistic test examples indicate that the new heuristic performed very well for each example.     

Single-pass and approximate dynamic-programming algorithms for order acceptance and capacity planning

This paper investigates dynamic order acceptance and capacity planning under limited regular and non-regular resources. Our goal is to maximize the profits of the accepted projects within a finite planning horizon. The way in which the projects are planned affects their payout time and, as a consequence, the reinvestment revenues as well as the available capacity for future arriving projects. In general, project proposals arise dynamically to the organization, and their actual characteristics are only revealed upon arrival. Dynamic solution approaches are therefore most likely to obtain good results. Although the problem can theoretically be solved to optimality as a stochastic dynamic program, real-life problem instances are too difficult to be solved exactly within a reasonable amount of time. Efficient and effective heuristics are thus required that supply a response without delay. For this reason, this paper considers both ‘single-pass’ algorithms as well as approximate dynamic-programming algorithms and investigates their suitability to solve the problem. Simulation experiments compare the performance of our procedures to a first-come, first-served policy that is commonly used in practice.     

Lagrangean relaxation based heuristics for lot sizing with setup times

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.     

A multi-period ordering and clearance pricing model considering the competition between new and out-of-season products

The joint management of pricing and inventory for perishable products has become an important problem for retailers. This paper investigates a multi-period ordering and clearance pricing model under consideration of the competition between new and out-of-season products. In each period, the ordering quantity of the new product and the clearance price of the out-of-season product are determined as decision variables before the demand is realized, and the unsold new product becomes the out-of-season one of the next period. We establish a finite-horizon Markov decision process model to formulate this problem and analyze its properties. A traditional dynamic program (DP) approach with two-dimensional search is provided. In addition, a myopic policy is derived in which only the profit of the current period is considered. Finally, we apply genetic algorithm (GA) to this problem and design a GA-based heuristic approach, showing by comparison among different algorithms that the GA-based heuristic approach is more performance sound than the myopic policy and much less time consuming than the DP approach.     

A new constructive heuristic for the flowshop scheduling problem

This paper presents a simple constructive heuristic (HFC) for the flowshop makespan problem which is capable of producing non-permutation schedules when it deems it appropriate. HFC determines the order of any two jobs in the final schedule based on their order in all two-machine problems embedded in the problem. Computational experiments indicate that HFC performs as well as NEH which is the currently best available constructive heuristic on problems where a permutation schedule is expected to be optimal. However, HFC outperforms NEH on problems where a non-permutation schedule may be optimal.     

A smoothing heuristic for a bilevel pricing problem

In this paper, we provide a heuristic procedure, that performs well from a global optimality point of view, for an important and difficult class of bilevel programs. The algorithm relies on an interior point approach that can be interpreted as a combination of smoothing and implicit programming techniques. Although the algorithm cannot guarantee global optimality, very good solutions can be obtained through the use of a suitable set of parameters. The algorithm has been tested on large-scale instances of a network pricing problem, an application that fits our modeling framework. Preliminary results show that on hard instances, our approach constitutes an alternative to solvers based on mixed 0–1 programming formulations.     

A fast heuristic for minimising total average cycle stock subject to practical constraints

We address a problem of setting reorder intervals (time supplies) of a population of items, subject to a restricted set of possible intervals as well as a limit on the total number of replenishments per unit time, both important practical constraints. We provide a dynamic programming formulation for obtaining the optimal solution. In addition, a simple and efficient heuristic algorithm has been developed. Computational experiments show that the performance of the heuristic is excellent based on a set of realistic examples.     

Price optimization with reference price effects: A generalized Benders’ decomposition method and a myopic heuristic approach

We consider a multi-period revenue maximization and pricing optimization problem in the presence of reference prices. We formulate the problem as a mixed integer nonlinear program and develop a generalized Benders’ decomposition algorithm to solve it. In addition, we propose a myopic heuristic and discuss the conditions under which it produces efficient solutions. We provide analytical results as well as numerical computations to illustrate the efficiency of the solution approaches as well as some managerial pricing insights.     

Advanced Genetic Programming Based Machine Learning

A Genetic Programming based approach for solving classification problems is presented in this paper. Classification is understood as the act of placing an object into a set of categories, based on the object’s properties; classification algorithms are designed to learn a function which maps a vector of object features into one of several classes. This is done by analyzing a set of input-output examples (“training samples”) of the function. Here we present a method based on the theory of Genetic Algorithms and Genetic Programming that interprets classification problems as optimization problems: Each presented instance of the classification problem is interpreted as an instance of an optimization problem, and a solution is found by a heuristic optimization algorithm. The major new aspects presented in this paper are advanced algorithmic concepts as well as suitable genetic operators for this problem class (mainly the creation of new hypotheses by merging already existing ones and their detailed evaluation). The experimental part of the paper documents the results produced using new hybrid variants of Genetic Algorithms as well as investigated parameter settings. Graphical analysis is done using a novel multiclass classifier analysis concept based on the theory of Receiver Operating Characteristic curves. The work described in this paper was done within the Translational Research Project L282 “GP-Based Techniques for the Design of Virtual Sensors” sponsored by the Austrian Science Fund (FWF).     

Jointly pricing and ordering for a multi-product multi-constraint newsvendor problem with supplier quantity discounts

We present an extension to the multi-product newsvendor problem by incorporating the retailer’s pricing decision as well as considering supplier quantity discount. The objective is to maximize the expected profit of the retailer through jointly determining the ordering quantities and selling prices for the products, subject to multiple capacity constraints. We formulate the problem as a Generalized Disjunctive Programming (GDP) model and develop a Lagrangian heuristic approach for its solution. Randomly produced instances involving up to 1000 products are used to test the proposed approach. Computational results show that the Lagrangian heuristic approach can present very good solutions to all instances in reasonable time.     

Novel evolutionary models and applications to sequence alignment problems

In this paper, we present a novel graph-theoretical approach for representing a wide variety of sequence analysis problems within a single model. The model allows incorporation of the operations “insertion”, “deletion”, and “substitution”, and various parameters such as relative distances and weights. Conceptually, we refer the problem as the minimum weight common mutated sequence (MWCMS) problem. The MWCMS model has many applications including multiple sequence alignment problem, the phylogenetic analysis, the DNA sequencing problem, and sequence comparison problem, which encompass a core set of very difficult problems in computational biology. Thus the model presented in this paper lays out a mathematical modeling framework that allows one to investigate theoretical and computational issues, and to forge new advances for these distinct, but related problems. Through the introduction of supernodes, and the multi-layer supergraph, we proved that MWCMS is -complete. Furthermore, it was shown that a conflict graph derived from the multi-layer supergraph has the property that a solution to the associated node-packing problem of the conflict graph corresponds to a solution of the MWCMS problem. In this case, we proved that when the number of input sequences is a constant, MWCMS is polynomial-time solvable. We also demonstrated that some well-known combinatorial problems can be viewed as special cases of the MWCMS problem. In particular, we presented theoretical results implied by the MWCMS theory for the minimum weight supersequence problem, the minimum weight superstring problem, and the longest common subsequence problem. Two integer programming formulations were presented and a simple yet elegant decomposition heuristic was introduced. The integer programming instances have proven to be computationally intensive. Consequently, research involving simultaneous column and row generation and parallel computing will be explored. The heuristic algorithm, introduced herein for multiple sequence alignment, overcomes the order-dependent drawbacks of many of the existing algorithms, and is capable of returning good sequence alignments within reasonable computational time. It is able to return the optimal alignment for multiple sequences of length less than 1500 base pairs within 30 minutes. Its algorithmic decomposition nature lends itself naturally for parallel distributed computing, and we continue to explore its flexibility and scalability in a massive parallel environment.     

A New Application of Incremental Analysis in Resource Allocations

This paper presents an optimization procedure which would offer a much simpler and faster procedure than dynamic programming in reaching optimal solutions for a special class of resource allocation problems. The solution method is based upon an incremental analysis and does not require further computation beyond the conversion of a payoff table to a table of marginal payoffs by simple subtractions. The optimality of the incremental solution will be demonstrated by a heuristic proof with several examples; and a numerical problem to illustrate the use of incremental analysis as well as to compare it with the solution procedure of dynamic programming will also be given.