Combinatorial Optimization

The Minimization of the Weighted Completion Time Variance in a Single Machine: A Specialized Cutting-Plane Approach

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling

This study addresses the problem of minimizing the weighted completion time variance (WCTV) in single-machine scheduling. Unlike the unweighted version, which has been extensively studied, the weighted variant introduces unique challenges due to the absence of theoretical properties that could guide the design of efficient algorithms. We propose a mathematical programming framework based on a … Read more

Recoverable Robust Cardinality Constrained Maximization with Commitment of a Submodular Function

Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part … Read more

Hic Sunt Dracones: The Structure of the Inverse-Feasible Region of a Multiobjective Integer Program

Categories Combinatorial Optimization, Integer Programming, Multi-Criteria Optimization Tags , ,

Optimization problems that involve multiple, conflicting criteria lead to a set of efficient solutions, and when there are discrete decisions, some solutions may be unsupported. Applications where it is difficult to estimate the parameters for criteria motivate inverse optimization techniques. We provide a theoretical analysis of the set of (unknown) objective parameters which lead to … Read more

Implied Integrality in Mixed-Integer Optimization

Categories (Mixed) Integer Linear Programming, Integer Programming, Polyhedra Tags , , , ,

Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this work we formalize the definition of implied integrality by taking a … Read more

Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem

Categories Graphs and Matroids, Integer Programming Tags , ,

We theoretically and computationally compare the strength of the two main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between either of the two upper bounds and the optimal value of the EWMCP is unbounded. This result … Read more

Novel closed-loop controllers for fractional linear quadratic tracking systems

Categories Applications - Science and Engineering, Approximation Algorithms, Systems governed by Differential Equations Optimization Tags , , , , ,

A new method for finding closed-loop optimal controllers of fractional tracking quadratic optimal control problems is introduced. The optimality conditions for the fractional optimal control problem are obtained. Illustrative examples are presented to show the applicability and capabilities of the method. ArticleDownload View PDF

Two approaches to piecewise affine approximation

Categories Applications - OR and Management Sciences, Approximation Algorithms, Data-Mining Tags , , ,

The problem of approximation by piecewise affine functions has been studied for several decades (least squares and uniform approximation). If the location of switches from one affine piece to another (knots for univariate approximation) is known the problem is convex and there are several approaches to solve this problem. If the location of such switches … Read more

A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

SDP bounds on the stability number via ADMM and intermediate levels of the Lasserre hierarchy

Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

We consider the Lasserre hierarchy for computing bounds on the stability number of graphs. The semidefinite programs (SDPs) arising from this hierarchy involve large matrix variables and many linear constraints, which makes them difficult to solve using interior-point methods. We propose solving these SDPs using the alternating direction method of multipliers (ADMM). When the second … Read more

A Computational Search for Minimal Obstruction Graphs for the Lovász–Schrijver SDP Hierarchy

Categories Combinatorial Optimization, Semi-definite Programming Tags ,

We study the lift-and-project relaxations of the stable set polytope of graphs generated by \( \text{LS}_+ \), the SDP lift-and-project operator devised by Lovász and Schrijver. In particular, we focus on searching for \( \ell \)-minimal graphs, which are graphs on $3\ell$ vertices whose stable set polytope has rank \( \ell \) with respect to … Read more