Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling

Pre-runtime scheduling of large-scale electronic systems, as those in modern aircraft, can be computationally challenging. In this paper, we study a distributed integrated modular avionic system of practical relevance where the scheduling includes to assign communication messages to time slots and to sequence tasks on modules. For this problem, the challenge is the huge number … Read more

Network Migration Problem: A Logic-based Benders Decomposition Driven by Column Generation and Constraint Programming

Telecommunication networks frequently face technological advancements and need to upgrade their infrastructure. Adapting legacy networks to the latest technology requires synchronized technicians responsible for migrating the equipment. The goal of the network migration problem is to find an optimal plan for this process. This is a defining step in the customer acquisition of telecommunications service … Read more

Mathematical models for the minimization of open stacks problem

In this paper, we address the Minimization of Open Stacks Problem (MOSP). This problem often appears during production planning of manufacturing industries, such as in the cutting of objects to comply with space constraints around the cutting machine in the glass, furniture, and metallurgical industries. The MOSP is also pertinent to the field of VLSI … Read more

Energy-efficient Automated Vertical Farms

Autonomous vertical farms (VFs) are becoming increasingly more popular, because they allow to grow food minimising water consumption and the use of pesticides, while greatly increasing the yield per square metre, compared with traditional agriculture. To meet sustainability goals, however, VFs must operate at maximum efficiency; it would be otherwise impossible to compete with the … Read more

Two-stage and one-group two-dimensional guillotine cutting problems with defects: a CP-based algorithm and ILP formulations

We address two variants of the two-dimensional guillotine cutting problem that appear in different manufacturing settings that cut defective objects. Real-world applications include the production of flat glass in the glass industry and the cutting of wooden boards with knotholes in the furniture industry. These variants assume that there are several defects in the object, … Read more

A new branch-and-filter exact algorithm for binary constraint satisfaction problems

A binary constraint satisfaction problem (BCSP) consist in determining an assignment of values to variables which is compatible with a set of constraints. The problem is called binary because the constraints involve only pairs of variables. The BCSP is a cornerstone problem in Constraint Programming (CP), appearing in a very wide range of real-world applications. … Read more

Optimal Steiner Trees Under Node and Edge Privacy Conflicts

In this work, we suggest concepts and solution methodologies for a series of strategic network design problems that find application in highly data-sensitive industries, such as, for instance, the high-tech, governmental, or military sector. Our focus is on the installation of widely used cost-efficient tree-structured communication infrastructure. As base model we use the well-known Steiner … Read more

Achieving Consistency with Cutting Planes

Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linear programming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching. A partial assignment is inconsistent with a constraint set when … Read more

Flexible Job Shop Scheduling Problems with Arbitrary Precedence Graphs

A common assumption in the shop scheduling literature is that the processing order of the operations of each job is sequential; however, in practice there can be multiple connections and finish-to-start dependencies among the operations of each job. This paper studies flexible job shop scheduling problems with arbitrary precedence graphs. Rigorous mixed integer and constraint … Read more

Constraint Programming Approaches for the Discretizable Molecular Distance Geometry Problem

The Distance Geometry Problem (DGP) seeks to find positions for a set of points in geometric space when some distances between pairs of these points are known. The so-called discretization assumptions allow to discretize the search space of DGP instances. In this paper, we focus on a key subclass of DGP, namely the Discretizable Molecular … Read more