mixed-integer linear programming – Page 5

Global Solutions of Nonconvex Standard Quadratic Programs via Mixed Integer Linear Programming Reformulations

Published: 2018/10/04

A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative mixed integer linear programming formulations. Our first formulation is based on casting a standard quadratic program … Read more

A Mixed Integer Linear Program for Optimizing the Utilization of Locomotives with Maintenance Constraints

Published: 2018/09/10

Applications - OR and Management Sciences, Scheduling locomotive scheduling problem, maintenance constraints, mixed-integer linear programming

In this paper we investigate the Locomotive Scheduling Problem, i.e., the optimization of locomotive utilization with prior known transports that must be performed. Since railway timetables are typically planned a year in advance, the aim is to assign locomotives to trains such that the locomotive utilization is maximized while maintenance constraints are taken into account. … Read more

On robust fractional 0-1 programming

Published: 2018/08/31, Updated: 2019/07/23

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Robust Optimization fractional 0-1 programming, mixed-integer linear programming, robust optimization

We study single- and multiple-ratio robust fractional 0-1 programming problems (RFPs). In particular, this work considers RFPs under a wide-range of disjoint and joint uncertainty sets, where the former implies separate uncertainty sets for each numerator and denominator, and the latter accounts for different forms of inter-relatedness between them. First, we demonstrate that, unlike the … Read more

The SCIP Optimization Suite 6.0

Published: 2018/07/02, Updated: 2018/07/03

Matthias Miltenberger

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming benders decomposition, branch-and-cut, branch-and-price, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization, steiner tree optimization

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion … Read more

Solution for short-term hydrothermal scheduling with a logarithmic size MILP formulation

Published: 2018/06/11

Jinbao Jian

Shanshan Pan

Linfeng Yang

Applications - Science and Engineering logarithmic size, mixed-integer linear programming, non-linear programming, piecewise linearize, short-term hydrothermal scheduling

Short-term hydrothermal scheduling (STHS) is a non-convex and non-differentiable optimization problem that is difficult to solve efficiently. One of the most popular strategy is to reformulate the complicated STHS by various linearization techniques that makes the problem easy to solve. However, in this process, a large number of extra continuous variables, binary variables and constraints … Read more

An Improved Flow-based Formulation and Reduction Principles for the Minimum Connectivity Inference Problem

Published: 2018/04/27, Updated: 2018/06/08

Applications - Science and Engineering, Combinatorial Optimization, Integer Programming minimum connectivity inference, mixed-integer linear programming, reduction rules, subset interconnection design

The Minimum Connectivity Inference (MCI) problem represents an NP-hard generalisation of the well-known minimum spanning tree problem and has been studied in different fields of research independently. Let an undirected complete graph and finitely many subsets (clusters) of its vertex set be given. Then, the MCI problem is to find a minimal subset of edges … Read more

Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control

Published: 2018/02/16, Updated: 2019/12/13

Sebastian Sager

Tobias Weber

Clemens Zeile

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization approximation methods and heuristics, mixed-integer linear programming, mixed-integer non-linear programming, optimal control, ordinary differential equations, switched dynamic systems

Solving mixed-integer nonlinear programs (MINLPs) is hard in theory and practice. Decomposing the nonlinear and the integer part seems promising from a computational point of view. In general, however, no bounds on the objective value gap can be guaranteed and iterative procedures with potentially many subproblems are necessary. The situation is different for mixed-integer optimal … Read more

Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks

Published: 2018/02/01, Updated: 2018/11/24

(Mixed) Integer Linear Programming, Applications - Science and Engineering, Robust Optimization discrete arc sizing, mixed-integer linear programming, network design, potential networks, robust optimization, scenario generation

We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to … Read more

Bounding and Counting Linear Regions of Deep Neural Networks

Published: 2018/01/08, Updated: 2018/06/09

Srikumar Ramalingam

Thiago Serra

Christian Tjandraatmadja

(Mixed) Integer Linear Programming, Statistics deep learning, linear regions, mixed-integer linear programming, piecewise-linear activations, solution couting

We investigate the complexity of deep neural networks (DNN) that represent piecewise linear (PWL) functions. In particular, we study the number of linear regions, i.e. pieces, that a PWL function represented by a DNN can attain, both theoretically and empirically. We present (i) tighter upper and lower bounds for the maximum number of linear regions … Read more

The SCIP Optimization Suite 5.0

Published: 2017/12/21, Updated: 2017/12/29