|
on Computational Economics |
|
Issue of 2020‒01‒20
eighteen papers chosen by |
| By: | Katrin Heßler (Johannes Gutenberg University Mainz); Stefan Irnich (Johannes Gutenberg University Mainz) |
| Abstract: | The soft-clustered vehicle-routing problem is a variant of the classical capacitated vehicle-routing problem (CVRP) in which customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. We introduce a novel symmetric formulation of the problem in which the clustering part is modeled with an asymmetric sub-model. We solve the new model with a branch-and-cut algorithm exploiting some known valid inequalities for the CVRP that can be adapted. In addition, we derive problem-speciï¬ c cutting planes and new heuristic and exact separation procedures. For square grid instances in the Euclidean plane, we provide lower-bounding techniques and a reduction scheme that is also applicable to the respective traveling salesman problem. In comprehensive computational test on standard benchmark instances, we compare the different formulations and separation strategies in order to determine a best performing algorithmic setup. The computational results with this branch-and-cut algorithm show that several previously open instances can now be solved to proven optimality. |
| Keywords: | vehicle routing, clustered customers, branch-and-cut |
| Date: | 2020–01–08 |
| URL: | http://d.repec.org/n?u=RePEc:jgu:wpaper:2001&r=all |
| By: | Nicolas Woloszko |
| Abstract: | The present paper develops Adaptive Trees, a new machine learning approach specifically designed for economic forecasting. Economic forecasting is made difficult by economic complexity, which implies non-linearities (multiple interactions and discontinuities) and unknown structural changes (the continuous change in the distribution of economic variables). The forecast methodology aims at addressing these challenges. The algorithm is said to be “adaptive” insofar as it adapts to the quantity of structural change it detects in the economy by giving more weight to more recent observations. The performance of the algorithm in forecasting GDP growth 3- to 12-months ahead is assessed through simulations in pseudo-real-time for six major economies (USA, UK, Germany, France, Japan, Italy). The performance of Adaptive Trees is on average broadly similar to forecasts obtained from the OECD’s Indicator Model and generally performs better than a simple AR(1) benchmark model as well as Random Forests and Gradient Boosted Trees. |
| Keywords: | business cycles, concept drift, feature engineering, forecasting, GDP growth, interpretable AI, machine learning, short-term forecasts, structural change |
| JEL: | C01 C18 C23 C45 C53 C63 E37 |
| Date: | 2020–01–16 |
| URL: | http://d.repec.org/n?u=RePEc:oec:ecoaaa:1593-en&r=all |
| By: | S Rojas Gonzalez; Inneke Van Nieuwenhuyse |
| Abstract: | We consider the multiobjective simulation optimization problem, where we seek to find the non-dominated set of designs evaluated using noisy simulation evaluations, in the context of numerically expensive simulators. We propose SKMOCBA, a metamodel-based approach built upon the famous ParEGO algorithm. Our approach mainly differentiates from similar algorithms in that we use stochastic kriging, which explicitly characterizes both the extrinsic uncertainty of the unknown response surface, and the intrinsic uncertainty inherent in a stochastic simulation. We additionally integrate the Multiobjective Optimal Computing Budget Allocation (MOCBA) procedure in view of maximizing the probability of selecting systems with the true best expected performance. We evaluate the performance of the algorithm using standard test functions for multiobjective optimizers, perturbed by heterogeneous noise. The experimental results show that the proposed method outperforms its deterministic counterpart based on well-known quality indicators and the members of the true Pareto set found. In addition, we measure the impact of using MOCBA to improve the accuracy of the algorithm during the identification of the observed Pareto front. |
| Date: | 2018–11 |
| URL: | http://d.repec.org/n?u=RePEc:ete:kbiper:629347&r=all |
| By: | Chao Han; Xinwei Wang; Guopeng Song; Roel Leus |
| Abstract: | Earth observation satellites (EOSs) are specially designed to collect images according to user requirements. Agile EOSs (AEOSs), with stronger attitude maneuverability, greatly improve the observation capability, while increasing the complexity of scheduling the observations. We are the first to address multiple AEOSs scheduling with multiple observations where the objective function aims to maximize the entire observation profit over a fixed horizon. The profit attained by multiple observations for each target is nonlinear in the number of observations. Our model is a specific interval scheduling problem, with each satellite orbit represented as a machine. A column-generation-based framework is developed for this problem, in which the pricing problems are solved using a label-setting algorithm. Extensive computational experimtents are conducted on the basis of one of China’s AEOS constellations. The results indicate that our optimality gap is less than 3% on average, which validates our framework. We also evaluate the performance of the framework for conventional EOS scheduling. |
| Keywords: | Agile Earth observation satellites, Integer programming, Column generation heuristic, Interval scheduling |
| Date: | 2018–10 |
| URL: | http://d.repec.org/n?u=RePEc:ete:kbiper:627938&r=all |
| By: | Çiflikli, Gökhan (London School of Economics and Political Science); Metternich, Nils W (University College London) |
| Abstract: | Efforts to predict civil war onset, its duration, and subsequent peace have dramatically increased. Nonetheless, by standard classification metrics the discipline seems to make little progress. Some remedy is promised by particular cross-validation strategies and machine learning tools, which increase accuracy rates substantively. However, in this research note we provide convincing evidence that the predictive performance of conflict models has been much better than previously assessed. We demonstrate that standard classification metrics for binary outcome data are prone to underestimate model performance in a binary-time-series-cross-section context. We argue for temporal residual based metrics to evaluate cross-validation efforts in binary-time-series-cross-section and test these in Monte Carlo experiments and existing empirical studies. |
| Date: | 2019–03–13 |
| URL: | http://d.repec.org/n?u=RePEc:osf:socarx:tvshu&r=all |
| By: | Christian Tilk (Johannes Gutenberg University Mainz); Asvin Goel (Kühne Logistics University) |
| Abstract: | This paper studies the vehicle routing and truck driver scheduling problem where routes and schedules must comply with hours of service regulations for truck drivers. It presents a backward labeling method for generating feasible schedules and shows how the labels generated with the backward method can be combined with labels generated by a forward labeling method. The bidirectional labeling is embedded into a branch and-price-and-cut approach and evaluated for hours of service regulations in the United States and the European Union. Computational experiments show that the resulting bidirectional branch-and-price-and-cut approach is signi?cantly faster than unidirectional counterparts and previous approaches. |
| Keywords: | Routing, Hours of service regulations, truck driver scheduling, bidirectional labeling, branch and-price-and-cut |
| Date: | 2019–07–15 |
| URL: | http://d.repec.org/n?u=RePEc:jgu:wpaper:1914&r=all |
| By: | Nan Hu; Jian Li; Alexis Meyer-Cirkel |
| Abstract: | We compared the predictive performance of a series of machine learning and traditional methods for monthly CDS spreads, using firms’ accounting-based, market-based and macroeconomics variables for a time period of 2006 to 2016. We find that ensemble machine learning methods (Bagging, Gradient Boosting and Random Forest) strongly outperform other estimators, and Bagging particularly stands out in terms of accuracy. Traditional credit risk models using OLS techniques have the lowest out-of-sample prediction accuracy. The results suggest that the non-linear machine learning methods, especially the ensemble methods, add considerable value to existent credit risk prediction accuracy and enable CDS shadow pricing for companies missing those securities. |
| Date: | 2019–12–27 |
| URL: | http://d.repec.org/n?u=RePEc:imf:imfwpa:19/292&r=all |
| By: | F Yang; Roel Leus |
| Abstract: | Hybrid flow shops can be encountered in various industrial settings. In this paper we develop methods for scheduling hybrid flow shops with hard time windows. Specifically, we study a two-stage hybrid flow shop scheduling problem with time windows to minimize the total weighted completion times. Each stage consists of one or more identical parallel machines, and each job visits two processing stages in series. Finding a feasible schedule with hard time windows is a challenging task in this setting, because it is NP-complete in the strong sense even for a single machine in a single stage. We propose two matheuristics to find an initial feasible solution by local branching. We also develop two schedule improvement procedures, one based on stage-by-stage decomposition, and one using adapted local branching. The performance of our methods is validated via extensive computational experiments. |
| Date: | 2018–11 |
| URL: | http://d.repec.org/n?u=RePEc:ete:kbiper:630069&r=all |
| By: | Vuong, Quan-Hoang |
| Abstract: | This paper proposes a new academic discipline of computational entrepreneurship, which centers on: i) An exponentially growing (and less expensive) computing power, to the extent that almost everybody in a modern society can own and use that; ii) Omnipresent high-speed Internet connectivity, wired or wireless, representing our modern day’s economic connectomics; iii) Growing concern of exploiting “serendipity” for a strategic commercial advantage; and, iv) Growing capabilities of lay people in performing calculations for their informed decisions in taking fast-moving entrepreneurial opportunities. Computational entrepreneurship has slowly become a new mode of operation for business ventures, and will likely bring the academic discipline of entrepreneurship back to mainstream economics. |
| Date: | 2018–12–19 |
| URL: | http://d.repec.org/n?u=RePEc:osf:osfxxx:kqbmg&r=all |
| By: | NESTEROV Yurii, (Université catholique de Louvain, CORE, Belgium); FLOREA Mihai I., (Université catholique de Louvain, CORE and INMA, Belgium) |
| Abstract: | In this paper, we consider gradient methods for minimizing smooth convex functions, which employ the information obtained at the previous iterations in order to accelerate the convergence towards the optimal solution. This information is used in the form of piece-wise linear model of the objective function, which provides us with much better prediction abilities as compared with the standard linear model. To the best of our knowledge, this approach was never really applied in Convex Minimization to differentiable functions in view of the high complexity of the corresponding auxiliary problems. However, we show that all necessary computations can be done very efficiently. Consequently, we get new optimization methods, which are better than the usual Gradient Methods both in the number of calls of oracle and in the computational time. Our theoretical conclusions are confirmed by preliminary computational experiments. |
| Keywords: | convex optimization, gradient methods, relative smoothness, rate of convergence piece-wise linear model |
| Date: | 2019–11–27 |
| URL: | http://d.repec.org/n?u=RePEc:cor:louvco:2019022&r=all |
| By: | Alexandre Miot; Gilles Drigout |
| Abstract: | Detecting structure in noisy time series is a difficult task. One intuitive feature is the notion of trend. From theoretical hints and using simulated time series, we empirically investigate the efficiency of standard recurrent neural networks (RNNs) to detect trends. We show the overall superiority and versatility of certain standard RNNs structures over various other estimators. These RNNs could be used as basic blocks to build more complex time series trend estimators. |
| Date: | 2019–12 |
| URL: | http://d.repec.org/n?u=RePEc:arx:papers:1912.04009&r=all |
| By: | Vuong, Quan-Hoang |
| Abstract: | This short manuscript proposes a new academic discipline of computational entrepreneurship, which centers on: i) An exponentially growing (and less expensive) computing power, to the extent that almost everybody in a modern society can own and use that; ii) Omnipresent high-speed Internet connectivity, wired or wireless, representing our modern day’s economic connectomics; iii) Growing concern of exploiting “serendipity” for a strategic commercial advantage; and, iv) Growing capabilities of lay people in performing calculations for their informed decisions in taking fast-moving entrepreneurial opportunities. |
| Date: | 2018–12–14 |
| URL: | http://d.repec.org/n?u=RePEc:osf:osfxxx:wq52p&r=all |
| By: | Daniel Ciganda (Max Planck Institute for Demographic Research, Rostock, Germany); Nicolas Todd (Max Planck Institute for Demographic Research, Rostock, Germany) |
| Keywords: | computational demography, fertility, forecasts |
| JEL: | J1 Z0 |
| Date: | 2019 |
| URL: | http://d.repec.org/n?u=RePEc:dem:wpaper:wp-2019-024&r=all |
| By: | WENINGER Dieter, (FAU Erlangen-Nürnberg); WOLSEY, Laurence, (Université catholique de Louvain, CORE, Belgium) |
| Abstract: | We consider problems of the form min{cx + hy: Ax + By ≥ b, x \in Z^n_+, y \in Y \subseteq R^p_+} that are foten treated using Benders' algorithm, but in which some of the y-variables are required to be integer. We present two algorithms that hopefully add to and clarify some of the algorithms proposed since the year 2000. Both are branch-and-cut algorithms solving linear programs by maintaining a strict separation between a Master problem in (x,\eta)-variables and a subproblem in the y-variables. The first involves nothing but the solution of linear programs, but involves branching in (x,y)-space. It is demonstrated on a small capacitated facility location problem with single-sourcing. The second restricted to problems with x \in {0,1}n n only requires branching in the x-space, but uses cutting planes in the subproblem based on the integrality of the y-variables that are converted/lifted into valid inequalities for the original problem in (x,y)-variables. For the latter algorithm we show how the lifting can be carried out trivially for several classes of cutting planes. A 0-1 knapsack problem is provided as an example. To terminate we consider how the information generated in the course of the algorithms can be used to carry out certain post-optimality analysis. |
| Keywords: | Benders’ algorithm, mixed-integer subproblems, branch-and-cut, value function |
| JEL: | H20 H31 H50 |
| Date: | 2019–11–18 |
| URL: | http://d.repec.org/n?u=RePEc:cor:louvco:2019020&r=all |
| By: | FLOREA Mihai I., (Université catholique de Louvain, CORE, Belgium) |
| Abstract: | The Inexact Gradient Method with Memory (IGMM) is able to considerably outperform the Gradient Method by employing a piecewise linear lower model on the smooth part of the objective. However, this model cannot be solved exactly and IGMM relies on an inaccuracy term d. The need for a bound on inexactness narrows the range of problems to which IGMM can be applied. In addition, d carries over to the worst-case convergence rate. In this work, we show how a simple modification of IGMM eliminates the reliance on d for convergence. The resulting Exact Gradient Method with Memory (EGMM) is as broadly applicable as the Bregman Distance Gradient Method (NoLips) and has a worst-case rate of O(1/k), recently shown to be optimal for its class. Moreover, the elimination of d allows us to accelerate EGMM without error accumulation, yielding an Accelerated Gradient Method with Memory (AGMM) possessing a worst-case rate of O(1/k2) on the largest subclass of problems for which acceleration is known to be attainable. Preliminary computational experiments show that the flexibility of our model enables EGMM to surpass IGMM in practical performance. The convergence speed of AGMM also consistently exceeds that of FGM, even with small bundles. |
| Keywords: | gradient method, bundle, piece-wise linear model, acceleration, Bregman distance, relative smoothness, composite problem |
| Date: | 2019–12–17 |
| URL: | http://d.repec.org/n?u=RePEc:cor:louvco:2019026&r=all |
| By: | Song Guopeng; Roel Leus |
| Abstract: | We study the resource loading problem, which arises in tactical capacity planning. It depicts a sketch of the usage of resources, and decides the execution intensity for the orders to be executed. We study various MIP formulations for this problem, including three time-indexed formulations and one based on Dantzig-Wolfe decomposition. The relaxation strength of the formulations is compared based on polyhedral analysis. Computational experiments for these formulations are also presented, showing their difference in performance for finding optimal integer solutions. |
| Keywords: | Capacity planning, Mixed integer programming, Time-indexed formulation, Dantzig-Wolfe decomposition, LP-relaxation |
| Date: | 2018 |
| URL: | http://d.repec.org/n?u=RePEc:ete:kbiper:626339&r=all |
| By: | Carla Van Riet; Erik Demeulemeester; Nancy Vansteenkiste; Frank Rademakers |
| Abstract: | The need for specialized anesthesia equipment for pediatric patients and the preference for audiovisual separation of pediatric and adult patients in the hospital can be addressed by separating pediatric surgeries in one or more fully equipped operating rooms (ORs). Although this separation benefits the equipment use, the planning of specialized anesthesiologists and the patient experience, its impact on patient scheduling has barely been studied. The aim of this study is to assess the feasibility of allocating OR sessions to pediatric patients with regards to keeping the access times of both adult and pediatric patients within acceptable limits and with regards to the change in several operational performance measures. Introducing these separate pediatric sessions obviously decreases the scheduling flexibility. The question is whether this decrease is acceptable compared to the benefits the separation offers. We assess several scenarios using a data-driven simulation model, based on a real academic hospital setting. The results show that the percentage of patients that are served within their due time is only slightly affected when looking at adult and pediatric patients together, but this percentage drops by 13 (s = 6.22) percentage points if we isolate the performance of the pediatric patients. This decrease for some disciplines can be as large as 69 percentage points. Therefore, from a planning point of view, it is advised to only organize pediatric sessions for the disciplines whose performance drop is acceptable. Alternatively, for future research, the capacity allocation could be optimized for each discipline individually to account for the discipline’s characteristics. Moreover, studies on the difference in patient experience would complement this study. |
| Keywords: | Operating room planning and scheduling, Pediatric patients, Simulation |
| Date: | 2018 |
| URL: | http://d.repec.org/n?u=RePEc:ete:kbiper:626539&r=all |
| By: | Tarek Alexander Hassan; Stephan Hollander; Laurence van Lent; Ahmed Tahoun |
| Abstract: | Using tools from computational linguistics, we construct new measures of the impact of Brexit on listed firms in the United States and around the world; these measures are based on the proportion of discussions in quarterly earnings conference calls on the costs, benefits, and risks associated with the UK's intention to leave the EU. We identify which firms expect to gain or lose from Brexit and which are most affected by Brexit uncertainty. We then estimate effects of the different types of Brexit exposure on firm-level outcomes. We find that the impact of Brexit-related uncertainty extends far beyond British or even European firms; US and international firms most exposed to Brexit uncertainty lost a substantial fraction of their market value and have also reduced hiring and investment. In addition to Brexit uncertainty (the second moment), we find that international firms overwhelmingly expect negative direct effects from Brexit (the first moment) should it come to pass. Most prominently, firms expect difficulties from regulatory divergence, reduced labor mobility, limited trade access, and the costs of post-Brexit operational adjustments. Consistent with the predictions of canonical theory, this negative sentiment is recognized and priced in stock markets but has not yet significantly affected firm actions. |
| JEL: | D8 E22 E24 E32 E6 F0 G18 G32 G38 H32 |
| Date: | 2020–01 |
| URL: | http://d.repec.org/n?u=RePEc:nbr:nberwo:26609&r=all |