QPLIB: A Library of Quadratic Programming Instances

This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very “varied” class of problems, comprising sub-classes of problems ranging from trivial to undecidable. Solution methods for QP are very diverse, ranging … Read more

A Complete Characterization of Disjunctive Conic Cuts for Mixed Integer Second Order Cone Optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization problem. We extend our prior work on disjunctive conic cuts, which has thus far been restricted to the case in which the intersection of the hyperplanes and … Read more

Three ideas for a Feasibility Pump for nonconvex MINLP

We describe an implementation of the Feasibility Pump heuristic for nonconvex MINLPs. Our implementation takes advantage of three novel techniques, which we discuss here: a hierarchy of procedures for obtaining an integer solution, a generalized definition of the distance function that takes into account the nonlinear character of the problem, and the insertion of linearization … Read more

Convex Hull Characterizations of Lexicographic Orderings

Given a p-dimensional nonnegative, integral vector α, this paper characterizes the convex hull of the set S of nonnegative, integral vectors x that is lexicographically less than or equal to α. To obtain a finite number of elements in S, the vectors x are restricted to be component-wise upper-bounded by an integral vector u. We … Read more

Lower bounding procedure for the Asymmetric Quadratic Traveling Salesman Problem

In this paper we consider the Asymmetric Quadratic Traveling Salesman Problem. Given a directed graph and a function that maps every pair of consecutive arcs to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs is minimum. We propose an extended … Read more

A Tight Lower Bound for the Adjacent Quadratic Assignment Problem

In this paper we address the Adjacent Quadratic Assignment Problem (AQAP) which is a variant of the QAP where the cost coefficient matrix has a particular structure. Motivated by strong lower bounds obtained by applying Reformulation Linearization Technique (RLT) to the classical QAP, we propose two special RLT representations for the problem. The first is … Read more

A branch-and-bound algorithm for biobjective mixed-integer programs

We propose a branch-and-bound (BB) algorithm for biobjective mixed-integer linear programs (BOMILPs). Our approach makes no assumption on the type of problem and we prove that it returns all Pareto points of a BOMILP. We discuss two techniques upon which the BB is based: fathoming rules to eliminate those subproblems that are guaranteed not to … Read more

Mixed-Integer Nonlinear Optimization

Many optimal decision problems in scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the quality of the final design or plan. These decision problems lead to mixed-integer nonlinear programming (MINLP) problems that combine the combinatorial difficulty of optimizing over discrete variable sets with the challenges of handling … Read more

On Families of Quadratic Surfaces Having Fixed Intersections with Two Hyperplanes

We investigate families of quadrics that have fixed intersections with two given hyper-planes. The cases when the two hyperplanes are parallel and when they are nonparallel are discussed. We show that these families can be described with only one parameter. In particular we show how the quadrics are transformed as the parameter changes. This research … Read more

A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization

We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more