Search

The aim of this paper is to compare the performance of a local solution technique—namely Sequential Linear Programming (SLP) employing random starting points—with state-of-the-art global solvers such as Baron and more sophisticated local solvers such as Sequential Quadratic Programming and Interior Point for the pooling problem. These problems can have many local optima, and we present a small example that illustrates how this can occur.We demonstrate that SLP—usually deemed obsolete since the arrival of fast reliable SQP solvers, Interior Point Methods and sophisticated global solvers—is still the method of choice for an important class of pooling problems when the criterion is the quality of the solution found within a given acceptable time budget. On this measure SLP significantly ourperforms all other tested algorithms.In addition we introduce a new formulation, the qq-formulation, for the case of fixed demands, that exclusively uses proportional variables. We compare the performance of SLP and the global solver Baron on the qq-formulation and other common formulations. While Baron with the qq-formulation generates weaker bounds than with the other formulations tested, for both SLP and Baron the qq-formulation finds the best solutions within a given time budget. The qq-formulation can be strengthened by pq-like cuts in which case the same bounds as for the pq-formulation are obtained. However the associated time penalty due to the additional constraints results in poorer solution quality within the time budget.

We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain $R$ of normalized dimensions of $1$ and $\rho\geq 1$, and distances are measured according to the Manhattan metric. We show that the family of 'balanced' facility configurations (in which the Voronoi cells of individual facilities are equalized with respect to a number of geometric properties) is considerably richer in this metric than for Euclidean distances. Our main result considers the 'One-Round Voronoi Game' with Manhattan distances, in which first player White and then player Black each place $n$ points in $R$; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if $\rho\geq n$; for all other cases, we present a winning strategy for Black., Comment: 22 pages, 16 figures

Optimizing maintenance scheduling is a major issue to improve the performance of hydropower plants. We study a system of several physical components of the same family: either a set of turbines, a set of transformers or a set of generators. The components share a common stock of spare parts and experience random failures that occur according to known failure distributions. We seek a deterministic preventive maintenance strategy that minimizes an expected cost depending on maintenance and forced outages of the system. The Auxiliary Problem Principle is used to decompose the original large-scale optimization problem into a sequence of independent subproblems of smaller dimension while ensuring their coordination. Each subproblem consists in optimizing the maintenance on a single component. Decomposition-coordination techniques are based on variational techniques but the maintenance optimization problem is a mixed-integer problem. Therefore, we relax the dynamics and the cost functions of the system. The resulting algorithm iteratively solves the subproblems on the relaxed system with a blackbox method and coordinates the components. Relaxation parameters have an important influence on the optimization and must be appropriately chosen. An admissible maintenance strategy is then derived from the resolution of the relaxed problem. We apply the decomposition algorithm on a system with 80 components. It outperforms the reference blackbox method applied directly on the original problem.

Annals of operations research (2021). doi:10.1007/s10479-021-04426-0, Published by Springer Science + Business Media B.V, Dordrecht [u.a.]

In the aftermath of a hurricane, humanitarian logistics plays a critical role in delivering relief items to the affected areas in a timely fashion. This paper proposes a novel stochastic look-ahead framework that implements a two-stage stochastic programming model in a rolling horizon approach to address the evolving uncertain logistics system state during the post-hurricane humanitarian logistics operations. The two-stage stochastic programming model that executes in this rolling horizon approach is formulated as a mixed-integer programming problem. The model aims to minimize the total cost incurred in the logistics operations, which consist of transportation cost and social cost. The social cost is measured as a function of deprivation for unsatisfied demand. Our extensive numerical results and sensitivity analysis demonstrate the effectiveness of the proposed approach in reducing the total cost incurred during the post-hurricane relief logistics operations compared to the two-stage stochastic programming model implemented in a static fashion.

Brain-Computer Interfaces (BCIs) are systems allowing people to interact with the environment bypassing the natural neuromuscular and hormonal outputs of the peripheral nervous system (PNS). These interfaces record a user's brain activity and translate it into control commands for external devices, thus providing the PNS with additional artificial outputs. In this framework, the BCIs based on the P300 Event-Related Potentials (ERP), which represent the electrical responses recorded from the brain after specific events or stimuli, have proven to be particularly successful and robust. The presence or the absence of a P300 evoked potential within the EEG features is determined through a classification algorithm. Linear classifiers such as SWLDA and SVM are the most used for ERPs' classification. Due to the low signal-to-noise ratio of the EEG signals, multiple stimulation sequences (a.k.a. iterations) are carried out and then averaged before the signals being classified. However, while augmenting the number of iterations improves the Signal-to-Noise Ratio (SNR), it also slows down the process. In the early studies, the number of iterations was fixed (no stopping), but recently, several early stopping strategies have been proposed in the literature to dynamically interrupt the stimulation sequence when a certain criterion is met to enhance the communication rate. In this work, we explore how to improve the classification performances in P300 based BCIs by combining optimization and machine learning. First, we propose a new decision function that aims at improving classification performances in terms of accuracy and Information Transfer Rate both in a no stopping and early stopping environment. Then, we propose a new SVM training problem that aims to facilitate the target-detection process. Our approach proves to be effective on several publicly available datasets., 32 pages, research article

This paper investigates the variance reduction techniques Antithetic Variates (AV) and Latin Hypercube Sampling (LHS) when used for sequential sampling in stochastic programming and presents a comparative computational study. It shows conditions under which the sequential sampling with AV and LHS satisfy finite stopping guarantees and are asymptotically valid, discussing LHS in detail. It computationally compares their use in both the sequential and non-sequential settings through a collection of two-stage stochastic linear programs with different characteristics. The numerical results show that while both AV and LHS can be preferable to random sampling in either setting, LHS typically dominates in the non-sequential setting while performing well sequentially and AV gains some advantages in the sequential setting. These results imply that, given the ease of implementation of these variance reduction techniques, armed with the same theoretical properties and improved empirical performance relative to random sampling, AV and LHS sequential procedures present attractive alternatives in practice for a class of stochastic programs.

International audience; Progressive Hedging is a popular decomposition algorithm for solving multi-stage stochastic optimization problems. A computational bottleneck of this algorithm is that all scenario subproblems have to be solved at each iteration. In this paper, we introduce randomized versions of the Progressive Hedging algorithm able to produce new iterates as soon as a single scenario subproblem is solved. Building on the relation between Progressive Hedging and monotone operators, we leverage recent results on randomized fixed point methods to derive and analyze the proposed methods. Finally, we release the corresponding code as an easy-to-use Julia toolbox and report computational experiments showing the practical interest of randomized algorithms, notably in a parallel context. Throughout the paper, we pay a special attention to presentation, stressing main ideas, avoiding extra-technicalities, in order to make the randomized methods accessible to a broad audience in the Operations Research community.

In this paper, we extend the previous method for solving inverse problems for steady-state equations using the Generalized Collage Theorem by searching for an approximation that not only minimizes the collage error but also maximizes the entropy and minimizes the sparsity. In this extended formulation, the parameter estimation minimization problem can be understood as a multiple criteria problem, with three different and conflicting criteria: The generalized collage error, the entropy associated with the unknown parameters, and the sparsity of the set of unknown parameters. We implement a scalarization technique to reduce the multiple criteria program to a single criterion one, by combining all objective functions with different trade-off weights. Numerical examples confirm that the collage method produces good, but sub-optimal, results. A relatively low-weighted entropy term allows for better approximations while the sparsity term decreases the complexity of the solution in terms of the number of elements in the basis.

Conditional Value-at-Risk (CVaR) and Value-at-Risk (VaR), also called the superquantile and quantile, are frequently used to characterize the tails of probability distribution's and are popular measures of risk. Buffered Probability of Exceedance (bPOE) is a recently introduced characterization of the tail which is the inverse of CVaR, much like the CDF is the inverse of the quantile. These quantities can prove very useful as the basis for a variety of risk-averse parametric engineering approaches. Their use, however, is often made difficult by the lack of well-known closed-form equations for calculating these quantities for commonly used probability distribution's. In this paper, we derive formulas for the superquantile and bPOE for a variety of common univariate probability distribution's. Besides providing a useful collection within a single reference, we use these formulas to incorporate the superquantile and bPOE into parametric procedures. In particular, we consider two: portfolio optimization and density estimation. First, when portfolio returns are assumed to follow particular distribution families, we show that finding the optimal portfolio via minimization of bPOE has advantages over superquantile minimization. We show that, given a fixed threshold, a single portfolio is the minimal bPOE portfolio for an entire class of distribution's simultaneously. Second, we apply our formulas to parametric density estimation and propose the method of superquantile's (MOS), a simple variation of the method of moment's (MM) where moment's are replaced by superquantile's at different confidence levels. With the freedom to select various combinations of confidence levels, MOS allows the user to focus the fitting procedure on different portions of the distribution, such as the tail when fitting heavy-tailed asymmetric data., Fixed typo in Proposition 5 (changed - to +) and added reference

This paper proposes a strategic model of pollution control. A firm, representative of the productive sector of a country, aims at maximizing its profits by expanding its production. Assuming that the output of production is proportional to the level of pollutants' emissions, the firm increases the level of pollution. The government of the country aims at minimizing the social costs due to the pollution, and introduces regulatory constraints on the emissions' level, which then effectively cap the output of production. Supposing that the firm and the government face both proportional and fixed costs in order to adopt their policies, we model the previous problem as a stochastic impulse two-person nonzero-sum game. The state variable of the game is the level of the output of production which evolves as a general linearly controlled one-dimensional Ito-diffusion. Following an educated guess, we first construct a pair of candidate equilibrium policies and of corresponding equilibrium values, and we then provide a set of sufficient conditions under which they indeed realize an equilibrium. Our results are complemented by a numerical study when the (uncontrolled) output of production evolves as a geometric Brownian motion, and the firm's operating profit and the government's running cost functions are of power type. An analysis of the dependency of the equilibrium policies and values on the model parameters yields interesting new behaviors that we explain as a consequence of the strategic interaction between the firm and the government., Comment: 26 pages; 14 figures; improved presentation of the results and modified a few proofs; Accepted for publication in Annals of Operations Research

The graph bisection problem is the problem of partitioning the vertex set of a graph into two sets of given sizes such that the sum of weights of edges joining these two sets is optimized. We present a semidefinite programming relaxation for the graph bisection problem with a matrix variable of order $n$ - the number of vertices of the graph - that is equivalent to the currently strongest semidefinite programming relaxation obtained by using vector lifting. The reduction in the size of the matrix variable enables us to impose additional valid inequalities to the relaxation in order to further strengthen it. The numerical results confirm that our simplified and strengthened semidefinite relaxation provides the currently strongest bound for the graph bisection problem in reasonable time., Comment: 10 pages

In several multiobjective decision problems Pairwise Comparison Matrices (PCM) are applied to evaluate the decision variants. The problem that arises very often is the inconsistency of a given PCM. In such a situation it is important to approximate the PCM with a consistent one. One of the approaches is to minimize the distance between the matrices, most often the Euclidean distance. In the paper we consider the problem of minimizing the maximum distance. After applying the logarithmic transformation we are able to formulate the obtained subproblem as a Shortest Path Problem and solve it more efficiently. We analyze the structure of the set of optimal solutions and prove some of its properties. This allows us to provide an iterative algorithm that results in a unique, Pareto-efficient solution.

We consider a non-atomic congestion game on a graph, with several classes of players. Each player wants to go from his origin vertex to his destination vertex at the minimum cost and all players of a given class share the same characteristics: cost functions on each arc, and origin–destination pair. Under some mild conditions, it is known that a Nash equilibrium exists, but the computation of such an equilibrium in the multiclass case is an open problem for general functions. We consider the specific case where the cost functions are affine. We show that this problem is polynomially solvable when the number of vertices and the number of classes are fixed. In particular, it shows that the parallel two-terminal case with a fixed number of classes is polynomially solvable. On a more practical side, we propose an extension of Lemke’s algorithm able to solve this problem.

Pairwise comparison matrix as a crucial component of AHP, presents the prefer- ence relations among alternatives. However, in many cases, the pairwise comparison matrix is difficult to complete, which obstructs the subsequent operations of the clas- sical AHP. In this paper, based on DEMATEL which has ability to derive the total relation matrix from direct relation matrix, a new completion method for incomplete pairwise comparison matrix is proposed. The proposed method provides a new per- spective to estimate the missing values with explicit physical meaning. Besides, the proposed method has low computational cost. This promising method has a wide application in multi-criteria decision-making., Comment: 29 pages

We study the polyhedral structure of the static probabilistic lot-sizing problem and propose valid inequalities that integrate information from the chance constraint and the binary setup variables. We prove that the proposed inequalities subsume existing inequalities for this problem, and they are facet-defining under certain conditions. In addition, we show that they give the convex hull description of a related stochastic lot-sizing problem. We propose a new formulation that exploits the simple recourse structure, which significantly reduces the number of variables and constraints of the deterministic equivalent program. This reformulation can be applied to general chance-constrained programs with simple recourse. The computational results show that the proposed inequalities and the new formulation are effective for the the static probabilistic lot-sizing problems.

A classical result in risk measure theory states that every coherent risk measure has a dual representation as the supremum of certain expected value over a risk envelope. We study this topic in more detail. The related issues include: 1. Set operations of risk envelopes and how they change the risk measures, 2. The structure of risk envelopes of popular risk measures, 3. Aversity of risk measures and its impact to risk envelopes, and 4. A connection between risk measures in stochastic optimization and uncertainty sets in robust optimization., Annals of Operations Research, 2017

In data envelopment analysis (DEA), the concept of efficiency is examined in either Farrell (DEA) or Pareto senses. In either of these senses, the efficiency status of a decision making unit (DMU) is classified as either weak or strong. It is well established that the strong DEA efficiency is both necessary and sufficient for achieving the Pareto efficiency. For the weak Pareto efficiency, however, the weak DEA efficiency is only sufficient, but not necessary in general. Therefore, a DEA-inefficient DMU can be either weakly Pareto efficient or Pareto inefficient. Motivated by this fact, we propose a new classification of DMUs in terms of both DEA and Pareto efficiencies. To make this classification, we first demonstrate that the Farrell efficiency is based on the notion of FGL dominance. Based on the concept of dominance, we then propose and substantiate an alternative single-stage method. Our method is computationally efficient since (i) it involves solving a unique single-stage model for each DMU, and (ii) it accomplishes the classification of DMUs in both input and output orientations simultaneously. Finally, we present a numerical example to illustrate our proposed method.

We consider the problem of minimizing costs in the generation unit commitment problem, a cornerstone in electric power system operations, while enforcing an N-k-e reliability criterion. This reliability criterion is a generalization of the well-known $N$-$k$ criterion, and dictates that at least $(1-e_ j)$ fraction of the total system demand must be met following the failures of $k$ or fewer system components. We refer to this problem as the Contingency-Constrained Unit Commitment problem, or CCUC. We present a mixed-integer programming formulation of the CCUC that accounts for both transmission and generation element failures. We propose novel cutting plane algorithms that avoid the need to explicitly consider an exponential number of contingencies. Computational studies are performed on several IEEE test systems and a simplified model of the Western US interconnection network, which demonstrate the effectiveness of our proposed methods relative to current state-of-the-art.

We propose the new Top-Dog-Index, a measure for the branch-dependent historic deviation of the supply data of apparel sizes from the sales data of a fashion discounter. A common approach is to estimate demand for sizes directly from the sales data. This approach may yield information for the demand for sizes if aggregated over all branches and products. However, as we will show in a real-world business case, this direct approach is in general not capable to provide information about each branch's individual demand for sizes: the supply per branch is so small that either the number of sales is statistically too small for a good estimate (early measurement) or there will be too much unsatisfied demand neglected in the sales data (late measurement). Moreover, in our real-world data we could not verify any of the demand distribution assumptions suggested in the literature. Our approach cannot estimate the demand for sizes directly. It can, however, individually measure for each branch the scarcest and the amplest sizes, aggregated over all products. This measurement can iteratively be used to adapt the size distributions in the pre-pack orders for the future. A real-world blind study shows the potential of this distribution free heuristic optimization approach: The gross yield measured in percent of gross value was almost one percentage point higher in the test-group branches than in the control-group branches., Comment: 22 pages, 15 figures

In [Bianco, L., Giuseppe C., and P. Reverberi. 2001. "A network based model for traffic sensor location with implications on O/D matrix estimates". Transportation Science 35(1):50-60.], the authors present the Sensor Location Problem: that of locating the minimum number of traffic sensors at intersections of a road network such that the traffic flow on the entire network can be determined. They offer a necessary and sufficient condition on the set of monitored nodes in order for the flow everywhere to be determined. In this paper, we present a counterexample that demonstrates that the condition is not actually sufficient (though it is still necessary). We present a stronger necessary condition for flow calculability, and show that it is a sufficient condition in a large class of graphs in which a particular subgraph is a tree. Many typical road networks are included in this category, and we show how our condition can be used to inform traffic sensor placement., Comment: Submitted for peer review on October 3, 2010

Decentralized stochastic control refers to the multi-stage optimization of a dynamical system by multiple controllers that have access to different information. Decentralization of information gives rise to new conceptual challenges that require new solution approaches. In this expository paper, we use the notion of an \emph{information-state} to explain the two commonly used solution approaches to decentralized control: the person-by-person approach and the common-information approach.

We describe an electoral system for distributing seats in a parliament. It gives proportionality for the political parties and close to proportionality for constituencies. The system suggested here is a version of the system used in Sweden and other Nordic countries with permanent seats in each constituency and adjustment seats to give proportionality on the national level. In the national election of 2010 the current Swedish system failed to give proportionality between parties. We examine here one possible cure for this unwanted behavior. The main difference compared to the current Swedish system is that the number of adjustment seats is not fixed, but rather dynamically determined to be as low as possible and still insure proportionality between parties., Comment: 16 pages, to appear in Annals of Operation Research