Optimization Software and Modeling Systems

DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization

  • Weizhu Chen
  • Qihang Lin
  • Lin Xiao
  • Wei Yu
    • Categories Convex and Nonsmooth Optimization, Parallel Algorithms Tags , , , , ,

    Machine learning with big data often involves large optimization models. For distributed optimization over a cluster of machines, frequent communication and synchronization of all model parameters (optimization variables) can be very costly. A promising solution is to use parameter servers to store different subsets of the model parameters, and update them asynchronously at different machines … Read more

    FPBH.jl: A Feasibility Pump Based Heuristic for Multi-objective Mixed Integer Linear Programming in Julia

  • Hadi Charkhgard
  • Aritra Pal
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Optimization Software and Modeling Systems Tags , , , ,

    Feasibility pump is one of the successful heuristic solution approaches developed almost a decade ago for computing high-quality feasible solutions of single-objective integer linear programs, and it is implemented in exact commercial solvers such as CPLEX and Gurobi. In this study, we present the first Feasibility Pump Based Heuristic (FPBH) approach for approximately generating nondominated … Read more

    Shaping and Trimming Branch-and-bound Trees

  • Philipp M. Christophel
  • Imre Pólik
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles Tags ,

    We present a new branch-and-bound type search method for mixed integer linear optimization problems based on the concept of offshoots (introduced in this paper). While similar to a classic branch-and-bound method, it allows for changing the order of the variables in a dive (shaping) and removing unnecessary branching variables from a dive (trimming). The regular … Read more

    On the effectiveness of primal and dual heuristics for the transportation problem

  • Jonas Schwinn
  • Ralf Werner
    • Categories Linear Programming, Optimization Software Benchmark

    The transportation problem is one of the most popular problems in linear programming. Over the course of time a multitude of exact solution methods and heuristics have been proposed. Due to substantial progress of exact solvers since the mid of the last century, the interest in heuristics for the transportation problem over the last few … Read more

    FOM — A MATLAB Toolbox of First Order Methods for Solving Convex Optimization Problems

  • Amir Beck
  • Nili Guttmann-Beck
    • Categories Optimization Software and Modeling Systems

    This paper presents the FOM MATLAB toolbox for solving convex optimization problems using first order methods. The diverse features of the eight solvers included in the package are illustrated through a collection of examples of different nature. Article Download View FOM — A MATLAB Toolbox of First Order Methods for Solving Convex Optimization Problems

    A Derivative-Free and Ready-to-Use NLP Solver for Matlab or Octave

  • Florian Jarre
  • Felix Lieder
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems Tags , ,

    This paper introduces a derivative-free and ready-to-use solver for nonlinear programs with nonlinear equality and inequality constraints (NLPs). Using finite differences and a sequential quadratic programming (SQP) approach, the algorithm aims at finding a local minimizer and no extra attempt is made to generate a globally optimal solution. Due to the use of finite differences, … Read more

    Parallel Solvers for Mixed Integer Linear Optimization

  • Timo Berthold
  • Thorsten Koch
  • Ted K. Ralphs
  • Yuji Shinano
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Parallel Algorithms Tags , , ,

    In this article, we provide an overview of the current state of the art with respect to solution of mixed integer linear optimization problems (MILPS) in parallel. Sequential algorithms for solving MILPs have improved substantially in the last two decades and commercial MILP solvers are now considered effective off-the-shelf tools for optimization. Although concerted development … Read more

    A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation

  • S.T. DeNegre
  • Ted K. Ralphs
  • S. Tahernejad
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … Read more

    Generation techniques for linear and integer programming instances with controllable properties

  • Davaatseren Baatar
  • Hans D Mittelmann
  • Simon Bowly
  • Kate Smith-Miles
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems Tags , ,

    This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable … Read more

    FiberSCIP – A shared memory parallelization of SCIP

  • Stefan Heinz
  • Yuji Shinano
  • Stefan Vigerske
  • Michael Winkler
    • Categories Integer Programming, Parallel Algorithms

    Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There … Read more