(Mixed) Integer Linear Programming

The two-echelon location-routing problem with time windows: Formulation, branch-and-price, and clustering

  • M. Saleh Farham
  • Cem Iyigun
  • Haldun Sural
    • Categories (Mixed) Integer Linear Programming, Transportation

    In this study, we consider the two-echelon location-routing problem with time windows (2E-LRPTW) to address the strategic and tactical decisions of the urban freight transportation. In the rst echelon, freights are delivered from city distribution centers (CDCs) to intermediate facilities, called satellites, in large batches. In the second echelon, goods are consolidated into smaller vehicles … Read more

    Testing Copositivity via Mixed-Integer Linear Programming

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory Tags , ,

    We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. Citation Dept. of Business … Read more

    Learning Optimal Classification Trees: Strong Max-Flow Formulations

  • Sina Aghaei
  • Andrés Gómez
  • Phebe Vayanos
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Statistics Tags , , ,

    We consider the problem of learning optimal binary classification trees. Literature on the topic has burgeoned in recent years, motivated both by the empirical suboptimality of heuristic approaches and the tremendous improvements in mixed-integer programming (MIP) technology. Yet, existing approaches from the literature do not leverage the power of MIP to its full extent. Indeed, … Read more

    Evaluating on-demand warehousing via dynamic facility location models

  • Kaan Unnu
  • Jennifer Pazour
    • Categories (Mixed) Integer Linear Programming, Supply Chain Management, Transportation Tags , , , , , ,

    On-demand warehousing platforms match companies with underutilized warehouse and distribution capabilities with customers who need extra space or distribution services. These new business models have unique advantages, in terms of reduced capacity and commitment granularity, but also have different cost structures compared to traditional ways of obtaining distribution capabilities. This research is the first quantitative … Read more

    Learning Generalized Strong Branching for Set Covering, Set Packing, and 0-1 Knapsack Problems

  • Yu Yang
  • Natashia Boland
  • Bistra Dilkina
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , ,

    Branching on a set of variables, rather than on a single variable, can give tighter bounds at the child nodes and can result in smaller search trees. However, selecting a good set of variables to branch on is even more challenging than selecting a good single variable to branch on. Generalized strong branching extends the … Read more

    Autonomous traffic at intersections: an optimization-based analysis of possible time, energy, and CO2 savings

  • Do Duc Le
  • Maximilian Merkert
  • Stephan Sorgatz
  • Mirko Hahn
  • Sebastian Sager
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Network Optimization Tags , , , , , ,

    In the growing field of autonomous driving, traffic-light controlled intersections as the nodes of large traffic networks are of special interest. We want to analyze how much an optimized coordination of vehicles and infrastructure can contribute to a more efficient transit through these bottlenecks. In addition, we are interested in sensitivity of the results with … Read more

    Integer packing sets form a well-quasi-ordering

  • Alberto Del Pia
  • Dion C. Gijswijt
  • Jeff Linderoth
  • Haoran Zhu
    • Categories (Mixed) Integer Linear Programming

    An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y ≤ x is in the set as well. Integer packing sets appear naturally in Integer Optimization. In fact, the set of integer points in … Read more

    Lossless Compression of Deep Neural Networks

  • Abhinav Kumar
  • Srikumar Ramalingam
  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering

    Deep neural networks have been successful in many predictive modeling tasks, such as image and language recognition, where large neural networks are often used to obtain good accuracy. Consequently, it is challenging to deploy these networks under limited computational resources, such as in mobile devices. In this work, we introduce an algorithm that removes units … Read more

    Exact and Heuristic Approaches for a New Circular Layout Problem

  • Truden Christian
  • Philipp Hungerländer
  • Kerstin Maier
  • Veronika Pachatz
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Production and Logistics Tags , , , ,

    We discuss a new facility layout problem, the so-called Directed Circular Facility Layout Problem (DCFLP). The DCFLP aims to find an optimal arrangement of machines on a circular material handling system such that the total weighted sum of the center-to-center distances between all pairs of machines measured in clockwise direction is minimized. Several real-world applications, … Read more

    Computational Aspects of Infeasibility Analysis in Mixed Integer Programming

  • Timo Berthold
  • Stefan Heinz
  • Jakob Witzig
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The … Read more