mixed-integer linear programming – Page 4

Mixed-Integer Optimal Control under Minimum Dwell Time Constraints

Published: 2019/09/13, Updated: 2020/10/29

Tailored mixed-integer optimal control policies for real-world applications usually have to avoid very short successive changes of the active integer control. Minimum dwell time constraints express this requirement and can be included into the combinatorial integral approximation decomposition, which solves mixed-integer optimal control problems by solving one continuous nonlinear program and one mixed-integer linear program. … Read more

Two-row and two-column mixed-integer presolve using hash-based pairing methods

Published: 2019/09/03, Updated: 2020/07/08

(Mixed) Integer Linear Programming, Optimization Software Benchmark, Polyhedra linear programming, mixed-integer linear programming, optimization solver, presolve

In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is … Read more

Multi-Row Intersection Cuts based on the Infinity Norm

Published: 2019/07/16

Ricardo Fukasawa

Laurent Poirrier

Alinson S. Xavier

(Mixed) Integer Linear Programming cutting planes, intersection cuts, mixed-integer linear programming

When generating multi-row intersection cuts for Mixed-Integer Linear Optimization problems, an important practical question is deciding which intersection cuts to use. Even when restricted to cuts that are facet-defining for the corner relaxation, the number of potential candidates is still very large, specially for instances of large size. In this paper, we introduce a subset … Read more

An Iterative Graph Expansion Approach for the Scheduling and Routing of Airplanes

Published: 2019/03/22

Armin Fügenschuh

Fabian Gnegel

(Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation dynamic graph expansion, mixed-integer linear programming, time-dependent airplane routing, vehicle routing

A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore the number … Read more

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

Published: 2018/10/04

Jacek Gondzio

E. Alper Yildirim

(Mixed) Integer Linear Programming, Quadratic Programming global optimization, mixed-integer linear programming, nonconvex optimization, quadratic programming

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