On Atomic Cliques in Temporal Graphs

Atomic cliques were introduced recently to analyze comorbidity graphs that vary over time. We consider the atomic counterpart of the classical maximum clique problem in this paper. Our main contribution is a polynomial-time algorithm that transforms the maximum atomic clique problem to the maximum clique problem on an auxiliary graph. We report results from our … Read more

Revisiting local branching with a machine learning lens

Finding high-quality solutions to mixed-integer linear programming problems (MILPs) is of great importance for many practical applications. In this respect, the refinement heuristic local branching (LB) has been proposed to produce improving solutions and has been highly influential for the development of local search methods in MILP. The algorithm iteratively explores a sequence of solution … Read more

Relaxations and Cutting Planes for Linear Programs with Complementarity Constraints

We study relaxations for linear programs with complementarity constraints, especially instances whose complementary pairs of variables are not independent. Our formulation is based on identifying vertex covers of the conflict graph of the instance and generalizes the extended reformulation-linearization technique of Nguyen, Richard, and Tawarmalani to instances with general complementarity conditions between variables. We demonstrate … Read more

Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump

The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate … Read more

Solving large-scale unit-commitment problems using dual dynamic programming and open-source solvers

The astonishing dimensions and complexity of power systems render them impossible to be managed without the help of cutting-edge software. Due to a lack of scalable, reliable and well documented free and open-source solutions, system operators, regulators, and government agencies often rely on proprietary software to provide them information that ultimately will be used to … Read more

Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs

The presence of symmetries of binary programs typically degrade the performance of branch-and-bound solvers. In this article, we derive efficient variable fixing algorithms to discard symmetric solutions from the search space based on propagation techniques for cyclic groups. Our algorithms come with the guarantee to find all possible variable fixings that can be derived from … Read more

Bounded variation in binary sequences

When addressing optimal control problems with binary switches varying over time, it often arises as a subproblem to optimize a linear function over the set of binary vectors of a given finite length satisfying certain practical constraints, such as a minimum dwell time or a bound on the number of switchings over the entire time … Read more

Rank-one Boolean tensor factorization and the multilinear polytope

We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the … Read more

Lower bound on size of branch-and-bound trees for solving lot-sizing problem

We show that there exists a family of instances of the lot-sizing problem, such that any branch-and-bound tree that solves them requires an exponential number of nodes, even in the case when the branchings are performed on general split disjunctions. Article Download View Lower bound on size of branch-and-bound trees for solving lot-sizing problem

Facets of the Total Matching Polytope for bipartite graphs

The Total Matching Polytope generalizes the Stable Set Polytope and the Matching Polytope. In this paper, we give the perfect formulation for Trees and we derive two new families of valid inequalities, the balanced biclique inequalities which are always facet-defining and the non-balanced lifted biclique inequalities obtained by a lifting procedure, which are facet-defining for … Read more