An optimal sequential procedure for a multiple selling problem with independent observations

We consider a sequential problem of selling K identical assets over the finite time horizon with a fixed number of offers per time period and no recall of past offers. The objective is to find an optimal sequential procedure which maximizes the total expected revenue. In this paper, we derive an effective number of stoppings for an optimal sequential procedure for the selling problem with independent observations.     

Maximum flow problem in wireless ad hoc networks with directional antennas

Directional antenna offers a variety of benefits for wireless networks, one of which is the increased spatial reuse ratio. This feature gives rise to the improved throughput in resource limited wireless ad hoc networks. In this paper, we formulate the maximum flow problem as an optimization problem in wireless ad hoc networks with switched beam directional antennas constrained by interference. We demonstrate how to solve this optimization problem. It turns out that the proposed method works for both single beam antenna and multi-beam antenna, with minor variation of the constraints.     

Modeling cooperation on a class of distribution problems

In this paper we study models of cooperation between the nodes of a network that represents a distribution problem. The distribution problem we propose arises when, over a graph, a group of nodes offers certain commodity, some other nodes require it and a third group of nodes neither need this material nor offer it but they are strategically relevant to the distribution plan. The delivery of one unit of material to a demand node generates a fixed profit, and the shipping of the material through the arcs has an associated cost. We show that in such a framework cooperation is beneficial for the different parties. We prove that the cooperative situation arising from this distribution problem is totally balanced by finding a set of stable allocations (in the core of an associated cooperative game). In order to overcome certain fairness problems of these solutions, we introduce two new solution concepts and study their properties.     

Global optimization of a nonconvex single facility location problem by sequential unconstrained convex minimization

The problem of maximizing the sum of certain composite functions, where each term is the composition of a convex decreasing function, bounded from below, with a convex function having compact level sets arises in certain single facility location problems with gauge distance functions. We show that this problem is equivalent to a convex maximization problem over a compact convex set and develop a specialized polyhedral annexation procedure to find a global solution for the case when the inside function is a polyhedral norm. As the problem was solved recently only for local solutions, this paper offers an algorithm for finding a global solution. Implementation and testing are not treated in this short communication.An earlier version of this paper appeared in the proceedings of a conference on Recent Advances in Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, 1991.     

A discrete long-term location–price problem under the assumption of discriminatory pricing: Formulations and parametric analysis

We consider a competitive location problem in which a new firm has to make decisions on the locations of several new facilities as well as on its price setting in order to maximise profit. Under the assumption of discriminatory prices, competing firms set a specific price for each market area. The customers buy one unit of a single homogeneous price-inelastic product from the facility that offers the lowest price in the area the consumers belong to. Three customer choice rules are considered in order to break ties in the offered prices. We prove that, considering long-term competition on price, this problem can be reduced to a problem with decisions on location only. For each one of the choice rules the location problem is formulated as an integer programming model and a parametric analysis of these models is given. To conclude, an application with real data is presented.     

A Simple Approach to the Discount Purchase Problem

In this paper we consider the problem of determining the optimal purchase quantity when the supplier offers a discount on large purchases. We propose a simple approach which requires fewer EOQ calculations for determining the lot size.     

Efficiency and compromise: a bid-offer–counteroffer mechanism with two players

A bid-offer–counteroffer mechanism is proposed to solve a fundamental two-person decision choice problem with two alternatives. It yields a unique subgame perfect equilibrium outcome, and leads to an intuitive overall solution that offers a reconciliation between egalitarianism and utilitarianism. We then investigate the axiomatic foundation of the solution. Furthermore, we compare it with several conventional strategic approaches to this setting.     

Production planning with approved vendor matrices for a hard-disk drive manufacturer

We develop an optimal production schedule for a manufacturer of hard-disk drives that offers its customers the approved vendor matrix (AVM) as a competitive advantage. An AVM allows each customer to pick and choose the various product component vendors for individual or pairs of components constituting their product. The production planning problem faced by the manufacturer is to meet customer demand as precisely as possible while observing the matrix restrictions and also the limited availability of production resources. We formulate this problem as a linear programming model with a large number of variables, and present a solution procedure based on the column generation technique. A special class of the problem is then studied, whereby the number of production setups in each period is limited and discrete. We modify our formulation into a mixed-integer problem, and proceed to develop procedures that can obtain good feasible solutions using linear programming rounding techniques.     

Guarantee structures for problems of fair division

We study the problem of fair division in situations where the number of individuals involved may vary while the resources at their disposal remain fixed. We are interested in minimizing the loss that an agent originally present may incur in such circumstances. Given a solution, i.e., a systematic method of solving any division problem in some class, we introduce the notion of its guarantee structure as a measure of the protection it offers to the original agents. We show that the Kalai-Smorodinsky solution offers greater guarantees than any weakly Pareto-optimal and anonymous solution and in particular than the Nash solution.     

Minimization of functionals on the solution of a large-scale discrete ill-posed problem

In this work we study the minimization of a linear functional defined on a set of approximate solutions of a discrete ill-posed problem. The primary application of interest is the computation of confidence intervals for components of the solution of such a problem. We exploit the technique introduced by Eldén in 1990, utilizing a parametric programming reformulation involving the solution of a sequence of quadratically constrained least squares problems. Our iterative method, which uses the connection between Lanczos bidiagonalization and Gauss-type quadrature rules to bound certain matrix functionals, is well-suited for large-scale problems, and offers a significant reduction in matrix-vector product evaluations relative to available methods.     

Optimal solution approximation for infinite positive-definite quadratic programming

We consider a general doubly-infinite, positive-definite, quadratic programming problem. We show that the sequence of unique optimal solutions to the natural finite-dimensional subproblems strongly converges to the unique optimal solution. This offers the opportunity to arbitrarily well approximate the infinite-dimensional optimal solution by numerically solving a sufficiently large finite-dimensional version of the problem. We then apply our results to a general time-varying, infinite-horizon, positive-definite, LQ control problem.This work was supported in part by the National Science Foundation under Grants ECS-8700836, DDM-9202849, and DDM-9214894.     

运输问题悖论及其研究

提出了运输问题的奇特现象——运输问题的悖论,讨论了运输问题悖论出现的条件,最后指出了研究运输问题悖论的现实意义.     

Optimal investment strategies for participating contracts

Participating contracts are popular insurance policies, in which the payoff to a policyholder is linked to the performance of a portfolio managed by the insurer. We consider the portfolio selection problem of an insurer that offers participating contracts and has an S-shaped utility function. Applying the martingale approach, closed-form solutions are obtained. The resulting optimal strategies are compared with portfolio insurance hedging strategies (CPPI and OBPI). We also study numerical solutions of the portfolio selection problem with constraints on the portfolio weights.     

Adaptive linear combination of heuristic orderings in constructing examination timetables

In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement.     

Non Parametric Distributed Inference in Sensor Networks Using Box Particles Messages

This paper deals with the problem of inference in distributed systems where the probability model is stored in a distributed fashion. Graphical models provide powerful tools for modeling this kind of problems. Inspired by the box particle filter which combines interval analysis with particle filtering to solve temporal inference problems, this paper introduces a belief propagation-like message-passing algorithm that uses bounded error methods to solve the inference problem defined on an arbitrary graphical model. We show the theoretic derivation of the novel algorithm and we test its performance on the problem of calibration in wireless sensor networks. That is the positioning of a number of randomly deployed sensors, according to some reference defined by a set of anchor nodes for which the positions are known a priori. The new algorithm, while achieving a better or similar performance, offers impressive reduction of the information circulating in the network and the needed computation times.     

Bayesian optimal knapsack procurement

A budget-constrained buyer wants to purchase items from a shortlisted set. Items are differentiated by observable quality and sellers have private reserve prices for their items. The buyer’s problem is to select a subset of maximal quality. Money does not enter the buyer’s objective function, but only his constraints. Sellers quote prices strategically, inducing a knapsack game. We report the Bayesian optimal mechanism for the buyer’s problem. We find that simultaneous take-it-or-leave-it offers are interim optimal.     

Reference sharing: a new collaboration model for cooperative coevolution

Cooperative coevolutionary algorithms have been a popular and effective learning approach to solve optimization problems through problem decomposition. However, their performance is highly sensitive to the degree of problem separability. Different collaboration mechanisms usually have to be chosen for particular problems. In the paper, we aim to design a collaboration model that can be successfully applied to a wide range of problems. We present a novel collaboration mechanism that offers this type of potential, along with a new sorting strategy for individuals that are assigned multiple fitness values. Furthermore, we demonstrate and analyze our algorithm through comparison studies with other popular cooperative coevolutionary models on a suite of standard function optimization problems.     

An interactive method for the optimal selection problem with two decision makers

We develop in this paper an interactive approach for the bilateral optimal selection problem. The decision model involves two decision makers (DMs) observing a sequence of n offers, sequentially, one at a time, in order to choose a compromise offer. Our method is based on an aggregation of the individual expected utilities of the two DMs whenever a conflict occurs. A conflicting situation arises when the two DMs do not agree to choose the same decision. We develop and simulate our approach on different forms of utilities.     

Multi-period price promotions in a single-supplier, multi-retailer supply chain under asymmetric demand information

This paper considers a two-stage supply chain in which a supplier serves a set of stores in a retail chain. We consider a two-stage Stackelberg game in which the supplier must set price discounts for each period of a finite planning horizon under uncertainty in retail-store demand. As a mechanism to stimulate sales, the supplier offers periodic off-invoice price discounts to the retail chain. Based on the price discounts offered by the supplier, and after store demand uncertainty is resolved, the retail chain determines individual store order quantities in each period. Because the supplier offers store-specific prices, the retailer may ship inventory between stores, a practice known as diverting. We demonstrate that, despite the resulting bullwhip effect and associated costs, a carefully designed price promotion scheme can improve the supplier’s profit when compared to the case of everyday low pricing (EDLP). We model this problem as a stochastic bilevel optimization problem with a bilinear objective at each level and with linear constraints. We provide an exact solution method based on a Reformulation-Linearization Technique (RLT). In addition, we compare our solution approach with a widely used heuristic and another exact solution method developed by Al-Khayyal (Eur. J. Oper. Res. 60(3):306–314, 1992) in order to benchmark its quality.     

An adjustment scheme for nonlinear pricing problem with two buyers

We examine a contracting problem with asymmetric information in a monopoly pricing setting. Traditionally, the problem is modeled as a one-period Bayesian game, where the incomplete information about the buyers’ preferences is handled with some subjective probability distribution. Here we suggest an iterative online method to solve the problem. We show that, when the buyers behave myopically, the seller can learn the optimal tariff by selling the product repeatedly. In a practical modification of the method, the seller offers linear tariffs and adjusts them until optimality is reached. The adjustment can be seen as gradient adjustment, and it can be done with limited information and so that it benefits both the seller and the buyers. Our method uses special features of the problem and it is easily implementable.