An extended algorithm for optimal product positioning

Optimal product positioning in an attribute space has been formulated according to the axiom of choice as a mixed integer nonlinear programming problem. To solve it, Albers and Brockhoff have designed the special purpose algorithm PROPOSAS. It works under simplified assumptions: Euclidean metric, equally weighted dimensions of the attribute space and equal sales per customer. The following article shows that the basic ideas of PROPOSAS are flexible enough to be expanded to cover a weighted Minkowski-metric as well as different revenues from the customers. Furthermore, the calculation of a new upper bound is described which reduces CPU-time considerably.     

Planning and coordination of production and distribution facilities for multiple commodities

We study an integrated logistics model for locating production and distribution facilities in a multi-echelon environment. Designing such logistics systems requires two essential decisions, one strategic (e.g., where to locate plants and warehouses) and the other operational (distribution strategy from plants to customer outlets through warehouses). The distribution strategy is influenced by the product mix at each plant, the shipments of raw material from vendors to manufacturing plants and the distribution of finished products from the plants to the different customer zones through a set of warehouses. First we provide a mixed integer programming formulation to the integrated model. Then, we present an efficient heuristic solution procedure that utilizes the solution generated from a Lagrangian relaxation of the problem. We use this heuristic procedure to evaluate the performance of the model with respect to solution quality and algorithm performance. Results of extensive tests on the solution procedure indicate that the solution method is both efficient and effective. Finally a `real-world' example is solved to explore the implications of the model.     

A-posteriori error analysis and adaptive finite element methods for singularly perturbed convection-diffusion equations

For singularly perturbed one-dimensional convection-diffusion equations, finite element approximations are constructed based on a so-called approximate symmetrization of the given unsymmetric problem. Local a-posteriori error estimates are established with respect to an appropriate energy norm where the bounds are proved to be realistic. The local bounds, called error indicators, provide a basis for a self-adaptive mesh refinement. For a model problem numerical results are presented showing that the adaptive method detects and resolves the boundary layer.     

Exact and heuristic methods for placing ships in locks

The ship placement problem constitutes a daily challenge for planners in tide river harbours. In essence, it entails positioning a set of ships into as few lock chambers as possible while satisfying a number of general and specific placement constraints. These constraints make the ship placement problem different from traditional 2D bin packing. A mathematical formulation for the problem is presented. In addition, a decomposition model is developed which allows for computing optimal solutions in a reasonable time. A multi-order best fit heuristic for the ship placement problem is introduced, and its performance is compared with that of the left-right-left-back heuristic. Experiments on simulated and real-life instances show that the multi-order best fit heuristic beats the other heuristics by a landslide, while maintaining comparable calculation times. Finally, the new heuristic’s optimality gap is small, while it clearly outperforms the exact approach with respect to calculation time.     

Developing an integrated model of an aluminium smelter incorporating sub-models with different time bases and levels of aggregation

In this paper an integrated production model of an aluminium smelter is discussed. The core model, i.e., the model involving the largest time base and highest level of aggregation of the production process, is a nonlinear bilevel programming problem. A number of smaller intermediate product modelling type mixed integer sub-models involving smaller time bases and lower levels of aggregation of the production process are important components of the overall integrated production model. It is shown that in order for the core integrated model of the smelter to be able to be specified with respect to some capacities, etc., and for the results of the integrated model to be implemented, these sub-models are necessary.     

Diffstrat: An analytical procedure for generating optimal new product concepts for a differentiated-type strategy

Firms are likely to consider employing multiple products in markets where competition and heterogeneity of consumer preferences suggest the use of market segmentation. The problem of identifying the optimal multiple new product concepts for such a market may be considered in either a sequential (one product at a time) or a simultaneous fashion. We show that the ‘optimal’ new product concepts generated sequentially are different from, and generality inferior to, those generated simultaneously. In this paper we present a new procedure, Diffstrat, which solves this problem of generating simultaneously optimal multiple new products for a wide range of consumer preference models. This procedure utilizes a fundamental insight called the augmented space approach to solve this problem.     

Star Product for Second-Class Constraint Systems from a BRST Theory

We propose an explicit construction of the deformation quantization of a general second-class constraint system that is covariant with respect to local coordinates on the phase space. The approach is based on constructing the effective first-class constraint (gauge) system equivalent to the original second-class constraint system and can also be understood as a far-reaching generalization of the Fedosov quantization. The effective gauge system is quantized by the BFV–BRST procedure. The star product for the Dirac bracket is explicitly constructed as the quantum multiplication of BRST observables. We introduce and explicitly construct a Dirac bracket counterpart of the symplectic connection, called the Dirac connection. We identify a particular star product associated with the Dirac connection for which the constraints are in the center of the respective star-commutator algebra. It is shown that when reduced to the constraint surface, this star product is a Fedosov star product on the constraint surface considered as a symplectic manifold.     

Covering a polygonal region by rectangles

The problem of covering a compact polygonal region, called target region, with a finite family of rectangles is considered. Tools for mathematical modeling of the problem are provided. Especially, a function, called Γ-function, is introduced which indicates whether the rectangles with respect to their configuration form a cover of the target region or not. The construction of the Γ-function is similar to that of Φ-functions which have been proved to be an efficient tool for packing problems. A mathematical model of the covering problem based on the Γ-function is proposed as well as a solution strategy. The approach is illustrated by an example and some computational results are presented.     

Protein structure optimization by side-chain positioning via beta-complex

A molecular structure determines a molecular function(s) and a correct understanding of molecular structure is important for biotechnology. The computational prediction of molecular structure is a frequent requirement for important biomolecular applications such as a homology modeling, a docking simulation, a protein design, etc. where the optimization of molecular structure is fundamental. One of the core problems in the optimization of protein structure is the optimization of side-chains called the side-chain positioning problem. The side-chain positioning problem, assuming the rigidity of backbone and a rotamer library, attempts to optimally assign a rotamer to each residue so that the potential energy of protein is minimized in its entirety. The optimal solution approach using (mixed) integer linear programming, with the dead-end elimination technique, suffers even for moderate-sized proteins because the side-chain positioning problem is NP-hard. On the other hand, popular heuristic approaches focusing on speed produce solutions of low quality. This paper presents an efficient algorithm, called the BetaSCP, for the side-chain positioning problem based on the beta-complex which is a derivative geometric construct of the Voronoi diagram. Placing a higher priority on solution quality, the BetaSCP algorithm produces a solution very close to the optima within a reasonable computation time. The effectiveness and efficiency of the BetaSCP are experimentally shown via a benchmark test against well-known algorithms using twenty test models selected from Protein Data Bank.     

Pricing used products for remanufacturing

Remanufacturing is one of recovery options for used products. As remanufacturing requires a continuous supply of used products, the economic incentive is required to attract customers to return their used products (called cores) and the problem of pricing a core becomes an important issue. Such a pricing problem is analogous to pricing an option, which can be used to sell the remanufactured cores (called core products). As sales price of core products follows a geometric Brownian motion, we propose a model here to evaluate the acquisition price of cores. This model links core acquisition price with the sale price of core product but assumes other costs such as logistics and remanufacturing to be deterministic. We have presented a numerical example to show its applicability. Since the model proposed here is generic, it is believed that the proposed model can be used in setting the core prices in many situations.     

Preventive maintenance scheduling of power generating units

The problem of preventive maintenance planning of electric power generating units can be formulated as a mixed-integer linear optimization problem. An extension of the model is presented to deal with more realistic assumptions about utilization of power resource. We propose a heuristic iterative exchange procedure to solve these problems. We introduce two methods to prevent jamming situations outside the feasible domain or at a local optimum. The first method is a recursive exchange procedure called multiple exchanges method and the second relies on Lagrangian relaxation. Furthermore, we compare these procedures with a tabu search.This research was supported by NSERC (Grant A8312) and FCAR (Grant ER-0289).Michèle Charest had an NSERC Scholarship to work on this project.     

Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion

We consider the problem of performing matrix completion with side information on row-by-row and column-by-column similarities. We build upon recent proposals for matrix estimation with smoothness constraints with respect to row and column graphs. We present a novel iterative procedure for directly minimizing an information criterion to select an appropriate amount of row and column smoothing, namely, to perform model selection. We also discuss how to exploit the special structure of the problem to scale up the estimation and model selection procedure via the Hutchinson estimator, combined with a stochastic Quasi-Newton approach. Supplementary material for this article is available online.     

Fast algorithms for robust classification with Bayesian nets

We focus on a well-known classification task with expert systems based on Bayesian networks: predicting the state of a target variable given an incomplete observation of the other variables in the network, i.e., an observation of a subset of all the possible variables. To provide conclusions robust to near-ignorance about the process that prevents some of the variables from being observed, it has recently been derived a new rule, called conservative updating. With this paper we address the problem to efficiently compute the conservative updating rule for robust classification with Bayesian networks. We show first that the general problem is NP-hard, thus establishing a fundamental limit to the possibility to do robust classification efficiently. Then we define a wide subclass of Bayesian networks that does admit efficient computation. We show this by developing a new classification algorithm for such a class, which extends substantially the limits of efficient computation with respect to the previously existing algorithm. The algorithm is formulated as a variable elimination procedure, whose computation time is linear in the input size.     

A two-dimensional strip cutting problem with sequencing constraint

We study a strip cutting problem that arises in the production of corrugated cardboard. In this context, rectangular items of different sizes are obtained by machines, called corrugators, that cut strips of large dimensions according to particular schemes containing at most two types of items. Because of buffer restrictions, these schemes have to be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet (sequencing constraint). We show that the problem of finding a set of schemes of minimum trim loss that satisfies an assigned demand for each item size is strongly NP-hard, even if the sequencing constraint is relaxed. Then, we present two heuristics for the problem with the sequencing constraint, both based on a graph characterization of the feasible solutions. The first heuristic is a two-phase procedure based on a mixed integer linear programming model. The second heuristic follows a completely combinatorial approach and consists of solving a suitable sequence of minimum cost matching problems. For both procedures, an upper bound on the number of schemes (setups) is found. Finally, a computational study comparing the quality of the heuristic solutions with respect to an LP lower bound is reported.     

Analysis of the Best Double Frequency Policy in the Single Link Problem with Discrete Shipping Times

We study an inventory–transportation problem where one product has to be shipped from an origin to a destination by vehicles of given capacity over an infinite time horizon. The product is made available at the origin and consumed at the destination at the same constant rate. The intershipment time must be not lower than a given minimum value. The problem is to decide when to make the shipments and how to load the vehicles to minimize the sum of the transportation and the inventory costs at the origin and at the destination per time unit. We study the case in which the intershipment time is a multiple of the minimum value, i.e., the problem with discrete shipping times. We show that, in this case, the best double frequency policy has a tight performance bound of about 1.1603 with respect to the optimal periodic policy and of about 1.1538 with respect to the best frequency-based policy. Moreover, we show that, from the worst-case point of view, the best double frequency policy is the optimal frequency-based policy.     

Optimal compactification of a floorplan and its relation to other optimization problems-a dynamic programming approach

We examine an algorithm for the compactification of an arrangement of rectangles in the plane as it is used for floorplans in the automated design of electronic circuits (also called sizing of floorplans). We reformulate this problem as a multistage decision problem and show that the algorithm is in fact the optimal solution obtained by the backward induction procedure of dynamic programing. The model allows generalisations to non-geometrical applications in scheduling and reliability.     

A tactical model for resource allocation and its application to advertising budgeting

Models for optimal product positioning have received considerable attention by marketing researchers and marketing scientists over the past decade. Typically, optimizing models take the viewpoint that the manager wishes to find a specific vector of product attribute levels that, in the face of competitors’ product profiles, maximizes the firm’s market share (or, perhaps, return) over some designated planning horizon. This class of models emphasizes long run strategic modeling.In contrast, the authors introduce a tactical, short-term model, called SALIENCE, whose purpose is to allocate sales efforts in such a way as to increase the relative importance of attributes for which the sponsoring firm’s current product has a (possibly temporary) differential advantage. In this case emphasis is on short-run, tactical decision making.We describe the SALIENCE model, both informally and mathematically. The model is applied, illustratively, to a real (disguised) study of overnight air shipment delivery.     

A new discrete Hopf–Rinow theorem

We prove a version of the Hopf–Rinow theorem with respect to path metrics on discrete spaces. The novel aspect is that we do not a priori assume local finiteness but isolate a local finiteness type condition, called essentially locally finite, that is indeed necessary. As a side product we identify the maximal weight, called the geodesic weight, generating the path metric in the situation when the space is complete with respect to any of the equivalent notions of completeness proven in the Hopf–Rinow theorem. As an application we characterize the graphs for which the resistance metric is a path metric induced by the graph structure.     

A Crop Planning Problem with Fuzzy Random Profit Coefficients

The main purpose of this paper is to present a crop planning problem for agricultural management under uncertainty. It is significant that agricultural managers assign their limited farmlands to cultivation of which crops in a season. This planning is called the crop planning problem and influences their incomes for the season. Usually, the crop planning problem is formulated as a linear programming problem. But there are many uncertain factors in agricultural problems, so future profits for crops are not certain values. A linear programming model with constant profit coefficients may not reflect the environment of decision making properly. Therefore, we propose a model of crop planning with fuzzy profit coefficients, and an effective solution procedure for the model. Furthermore, we extend this fuzzy model, setting the profit coefficients as discrete randomized fuzzy numbers. We show concrete optimal solutions for each models.     

A Combinatorial Approach to Piecewise Linear Time Series Analysis

Over recent years, several nonlinear time series models have been proposed in the literature. One model that has found a large number of successful applications is the threshold autoregressive model (TAR). The TAR model is a piecewise linear process whose central idea is to change the parameters of a linear autoregressive model according to the value of an observable variable, called the threshold variable. If this variable is a lagged value of the time series, the model is called a self-exciting threshold autoregressive (SETAR) model. In this article, we propose a heuristic to estimate a more general SETAR model, where the thresholds are multivariate. We formulate the task of finding multivariate thresholds as a combinatorial optimization problem. We develop an algorithm based on a greedy randomized adaptive search procedure (GRASP) to solve the problem. GRASP is an iterative randomized sampling technique that has been shown to quickly produce good quality solutions for a wide variety of optimization problems. The proposed model performs well on both simulated and real data.