Search

Given an undirected connected graph G = ( V , E ) , the minimum linear arrangement problem (MinLA) consists in determining a permutation π ≔ ( π 1 , … , π n ) of the node-set V = { 1 , … , n } , which minimizes the sum of edge costs | π i − π j | over all edges { i , j } ∈ E . We introduce a compact quadratic formulation, prove its correctness, and generate new mixed-integer linear formulations that require a very small number of variables and constraints. The idea behind the way we model permutations allows the development of strong valid constraints to strengthen the new formulations. We also adapt some cutting plane procedures from the literature to one of the new models. Computational experiments with benchmark and new instances are very encouraging and improve state-of-the-art solution approaches from the literature.

A legal dominating sequence of a graph is an ordered dominating set of vertices where each element dominates at least another one not dominated by its predecessors in the sequence. The length of a largest legal dominating sequence is called Grundy domination number. In this work, we introduce a generalized version of the Grundy domination problem. We explicitly calculate the corresponding parameter for paths and web graphs. We propose integer programming formulations for the new problem, find families of valid inequalities and perform extensive computational experiments to compare the formulations as well as to test these inequalities as cuts in a branch-and-cut framework. We also design and evaluate the performance of a heuristic for finding good initial lower and upper bounds and a tabu search that improves the initial lower bound. The test instances include randomly generated graphs, structured graphs, classical benchmark instances and two instances from a real application. Our approach is exact for graphs with 20–50 vertices and provides good solutions for graphs up to 10 000 vertices.

Consider an arc-capacitated network $$\mathcal {N}$$ through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multigraph with the same vertices as $$\mathcal {N}$$ and an edge for each arc of $$\mathcal {N}$$ , where the edge multiplicity is the flow in the respective arc. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of $$\mathcal {N}$$ , i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining on $$\mathcal {N}$$ a feasible flow such that its maximum flow degree is minimum. We present a polynomial time algorithm for this problem. We use its optimum value to derive an improved upper bound for the flow coloring problem (FCP), which consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index. Based on this procedure, we design an approximation algorithm for the FCP that improves the best known approximation factor.

We apply the t-linearization technique to the maximum diversity problem (MDP) and compare its performance with other well-known linearizations. We lift the t-constraints based on the cardinality restriction, derive valid inequalities for MDP, and show their usefulness to solve the problem within the t-linearization framework. We propose and computationally evaluate a branch-and-bound algorithm on benchmark instances. The algorithm is compared with other exact approaches from the literature.

We introduce the Generalized Dependency Constrained Spanning Tree Problem (G-DCST), where an edge can be chosen only if the number of edges chosen from its dependency set lies in a certain interval. The dependency relations between the edges of the input graph G are described by the input digraph D, whose vertices are the edges of G. The in-neighbors of a vertex of D form its dependency set. We show that G-DCST unifies and generalizes some known spanning tree problems that apply conflict constraints over edges or lower and upper bounds on vertex degrees. We show that the feasibility version of G-DCST is NP-complete even under strong restrictions on the structures of G and D as well as on the functions that define the minimum or maximum number of dependencies to be satisfied. We also show that this problem keeps an lnn inapproximability threshold under tight assumptions over G and D. On the other hand, we spot a polynomial case via a matroid intersection argument.

Given a graph $G$ and a digraph $D$ whose vertices are the edges of $G$, we investigate the problem of finding a spanning tree of $G$ that satisfies the constraints imposed by $D$. The restrictions to add an edge in the tree depend on its neighborhood in $D$. Here, we generalize previously investigated problems by also considering as input functions $\ell$ and $u$ on $E(G)$ that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by \texttt{G-DCST}, while the optimization problem is denoted by \texttt{G-DCMST}. We show that \texttt{G-DCST} is NP-complete even under strong assumptions on the structures of $G$ and $D$, as well as on functions $\ell$ and $u$. On the positive side, we prove two polynomial results, one for \texttt{G-DCST} and another for \texttt{G-DCMST}, and also give a simple exponential-time algorithm along with a proof that it is asymptotically optimal under the \ETH. Finally, we prove that other previously studied constrained spanning tree (\textsc{CST}) problems can be modeled within our framework, namely, the \textsc{Conflict CST}, the \textsc{Forcing CS, the \textsc{At Least One/All Dependency CST}, the \textsc{Maximum Degree CST}, the \textsc{Minimum Degree CST}, and the \textsc{Fixed-Leaves Minimum Degree CST}., Comment: 28 pages, 6 figures

Consideramos o problema da Floresta Geradora k-Rotulada, que consiste em encontrar uma floresta geradora de um grafo colorido em arestas com a menor quantidade de árvores e no máximo k cores. Derivamos duas caracterizações para o problema e mostramos estratégias para converter uma instância em outra equivalente. Esses resultados impactam o desenvolvimento de abordagens de solução. Identificamos também alguns casos polinomiais.

Based on the sociometric analysis of social networks, we introduce the sociotechnical teams formation problem (STFP). Given a group of individuals with different skill-sets and a social network that captures the mutual affinity between them, the problem consists in finding a set of pairwise disjoint teams, as harmonious as possible, with a minimum specified number of individuals per team per skill. We prove that STFP is $$\mathcal {NP}$$-hard and propose an integer linear programming formulation. We show several classes of facet-inducing inequalities for the corresponding polytope. Computational experiments performed on a set of 120 test instances attest the efficiency of a solution method based on the formulation strengthened by valid inequalities and on a simulated annealing algorithm used to provide good initial feasible solutions.

Given a group of individuals, each one with a single skill, and a social network capturing the mutual affinity among them, the Multiple Team Formation Problem (MTFP) consists in finding a set of teams, as harmonious as possible, each one comprising a given number of required skills. Dedication time of individuals can be partitioned into time fractions, thus allowing an individual to work in more than one team. In this work, we propose an Integer Linear Programming (ILP) formulation and sets of valid inequalities for the problem. Computational experiments carried out on test instances, generated according to the literature or based on real-world social networks, attest that the ILP model strengthened by valid inequalities consistently outperforms the existing quadratic formulation for MTFP.

Let G = (V, E) be a simple undirected graph. Given distinct labels in { 1 , ⋯ , | V | } to the vertices of G, we define the weight of an edge u v ∈ E as the absolute difference between the labels assigned to u and v. The minimum linear arrangement problem (MinLA) consists in finding a labeling of the vertices of G such that the sum of the weights of its edges is minimized. It is an NP-Hard problem whose corresponding polyhedron has a factorial number of extreme points. We propose a quadratic model for MinLA and use it to obtain a novel compact mixed integer linear programming (MILP) formulation for the problem, featuring O ( | V | 2 ) variables and O ( | V | 2 ) constraints. We show the correctness of the new model and discuss valid inequalities for the problem. Our findings open new insights on the study of effective exact approaches to the problem. Computational experiments show that the new quadratic and mixed linear models performed better than existing ones in the literature for new and benchmark instances of this problem.

A sequence of vertices in a graph is called a (total) legal dominating sequence if every vertex in the sequence (totally) dominates at least one vertex not dominated by the ones that precedes it, and at the end all vertices of the graph are (totally) dominated. The Grundy (total) domination number of a graph is the size of the largest (total) legal dominating sequence. In this work, we present integer programming formulations for obtaining the Grundy (total) domination number of a graph, we study some aspects of the polyhedral structure of one of them and we test the performance of some new valid inequalities as cuts. Fil: Campêlo, Manoel. Universidade Federal Do Ceará; Brasil Fil: Severin, Daniel Esteban. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

Motivated by the significant advances in integer optimization in the past decade, Bertsimas and Shioda developed an integer optimization method to the classical statistical problem of classification in a multidimensional space, delivering a software package called CRIO (Classification and Regression via Integer Optimization). Following those ideas, we define a new classification problem, exploring its combinatorial aspects. That problem is defined on graphs using the geodesic convexity as an analogy of the Euclidean convexity in the multidimensional space. We denote such a problem by Geodesic Classification (GC) problem. We propose an integer programming formulation for the GC problem along with a branch-and-cut algorithm to solve it. Finally, we show computational experiments in order to evaluate the combinatorial optimization efficiency and classification accuracy of the proposed approach., SCOPUS: cp.j, info:eu-repo/semantics/published

A k -fold x -coloring of a graph G is an assignment of (at least) k distinct colors from the set { 1 , 2 , ź , x } to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The k th chromatic number ofź G , denoted byź ź k ( G ) , is the smallest x such that G admits a k -fold x -coloring. We present an integer linear programming formulation (ILP) to determine ź k ( G ) and study the facial structure of the corresponding polytope P k ( G ) . We show facets thatź P k + 1 ( G ) inherits from P k ( G ) and show how to lift facets from P k ( G ) to P k + ź ( G ) . We project facets of P 1 ( G ź K k ) into facets of P k ( G ) , where G ź K k is the lexicographic product of G by a clique with k vertices. In both cases, we can obtain facet-defining inequalities from many of those known for the 1 -fold coloring polytope. We also derive facets of P k ( G ) from facets of stable set polytopes of subgraphs of G . In addition, we present classes of facet-defining inequalities based on strongly ź k -critical webs and antiwebs, which extend and generalize known results for 1 -fold coloring. We introduce this criticality concept and characterize the webs and antiwebs having such a property.

Motivated by bandwidth allocation under interference constraints in radio networks, we define and investigate an optimization problem that combines the classical flow and edge coloring problems in graphs. Let G = ( V , E ) be a graph with a demand function b : V ? Z + and a gateway g ? V ? V s , where V s = { v ? V : b ( v ) 0 } is the set of source nodes. A flow ? u of a source node u is a multiset of b ( u ) paths in G from u to g . A flow ? on G is a set with one flow for each source node. Every flow ? defines a multigraph G ? with vertex set V and all edges in the paths in ? . A distance- d edge coloring of a flow ? is an edge coloring of G ? such that two edges with the same color are at distance at least d in G . The distance- d flow coloring problem ( F C P d ) is the problem of obtaining a flow ? on G with a distance- d edge coloring where the number of used colors is minimum. For any fixed d ? 3 , we prove that F C P d is NP-hard even on a bipartite graph with just one source node. For d = 2 , we also prove NP-hardness on a bipartite graph with multiples sources. For d = 1 , we show that the problem is polynomial in 3-connected graphs and bipartite graphs. Finally, we show that a list version of the problem is inapproximable in polynomial time by a factor of O ( log n ) even on n -vertex paths, for any d ? 1 .

Um subconjunto de vértices S em um grafo G = (V, E) é convexo na convexidade P3 (resp. P 3⇤ ) se todo vértice v 2 V (G) \ S não possuir dois vizinhos (resp. que não sejam adjacentes entre si) em S. A envoltória convexa de S é o menor conjunto convexo que o contém. Um conjunto de envoltória é um conjunto cuja envoltória convexa é V (G). O número de envoltória é a cardinalidade de um conjunto de envoltória mínimo. Neste trabalho, propomos e estudamos duas formulações de programação linear-inteira para determinar o número de envoltória de um grafo nas convexidades P3 e P 3⇤ , que acreditamos serem as primeiras na literatura. Realizamos experimentos computacionais para avaliar seus desempenhos.

We apply the t-linearization to the straightforward 0 1 quadratic model for the maximum diversity problem. We computationally compare the obtained model with two other linear formulations from the literature. Computational experiments show that the t-linearization generates, on average, fewer constraints than the formulations, in addition to achieving a tighter upper bound in all used instances. On the other hand, one of the formulations can be slightly faster in obtaining the bounds.

Given a graph with an arbitrary vertex coloring, the Convex Recoloring Problem (CR) consists in recoloring the minimum number of vertices so that each color induces a connected subgraph. We focus on the complexity and inapproximability of this problem on k-colored graphs, for fixed k ⩾ 2 . We prove a strong complexity result showing that, for each k ⩾ 2 , CR is already NP-hard on k-colored grids, and therefore also on planar graphs with maximum degree 4. For each k ⩾ 2 , we prove that, for a positive constant c, there is no c ln n -approximation algorithm for k-colored n-vertex (bipartite) graphs, unless P = NP . We also prove that CR parameterized by the number of color changes is W [ 2 ] -hard. For 2-colored ( q , q − 4 ) -graphs, a class that includes cographs and P 4 -sparse graphs, we present linear-time algorithms for fixed q. The same complexity and inapproximability results are obtained for two relaxations of the problem, where only one fixed color or any color is required to induce a connected subgraph, respectively.

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.

A k -fold x -coloring of a graph G is an assignment of (at least) k distinct colors from the set { 1 , 2 , … , x } to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The k -th chromatic number of G , denoted by χ k ( G ) , is the smallest x such that G admits a k -fold x -coloring. We present an ILP formulation to determine χ k ( G ) and study the facial structure of the corresponding polytope P k ( G ) . We show facets that P k + 1 ( G ) inherits from P k ( G ) . We also relate P k ( G ) to P 1 ( G ∘ K k ) , where G ∘ K k is the lexicographic product of G by a clique with k vertices. In both cases, we can obtain facet-defining inequalities from many of those known for the 1-fold coloring polytope. In addition, we present a class of facet-defining inequalities based on strongly χ k -critical webs, which extend and generalize known corresponding results for 1-fold coloring. We introduce this criticality concept and characerize the webs having such a property.

Given a graph G = (V, E), a family of nonempty vertex-subsets S ⊆ 2 V , and a weight w : S → R+, the maximum stable set problem with weights on vertex-subsets consists in finding a stable set I of G maximizing the sum of the weights of the sets in S that intersect I. This problem arises within a natural column generation approach for the vertex coloring problem. In this work we perform an initial polyhedral study of this problem, by introducing a natural integer programming formulation and studying the associated polytope. We address general facts on this polytope including some lifting results, we provide connections with the stable set polytope, and we present three families of facet-inducing inequalities. Fil: Campêlo, Manoel. Universidade Federal do Ceará; Brasil Fil: Campos, Victor A.. Universidade Federal do Ceará; Brasil Fil: Corrêa, Ricardo C.. Universidade Federal do Ceará; Brasil Fil: Delle Donne, Diego Andrés. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Marenco, Javier Leonardo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina Fil: Mydlarz, Marcelo. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

A coloring of the vertices of a graph $$G$$G is convex if the vertices receiving a common color induce a connected subgraph of $$G$$G. We address the convex recoloring problem: given a graph $$G$$G and a coloring of its vertices, recolor a minimum number of vertices of $$G$$G, so that the resulting coloring is convex. This problem is known to be $$\fancyscript{NP}$$NP-hard even when $$G$$G is a path. We show an integer programming formulation for arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We consider instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to $$1500$$1500 vertices in 2 h, comparing favorably to other approaches that have been proposed in the literature.

We introduce a new facet-generating procedure for the stable set polytope, based on replacing ( k − 1 )-cliques with certain k-partite graphs, which subsumes previous procedures based on replacing vertices with stars, and thus also many others in the literature. It can be used to generate new classes of facet-defining inequalities.

We propose an integer programming formulation for the problem of finding the maximum k-partite induced sub-graph of a graph G based on representatives of stable sets. We investigate upper bounds provided by the solution, via a parallel sub-gradient algorithm, of a Lagrangian decomposition that breaks up this formulation into maximum weighted stable set problems for sub-graphs of G. Some computational experiments were carried out with an effective multi-threaded parallel implementation in a multi-core system, and their results are presented.

We consider the set of integral solutions of A x ⩽ b , x ⩾ 0 , where A is the edge-vertex incidence matrix of a bidirected graph. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived as fractional Gomory cuts. It follows in particular that the split closure is equal to the Chvatal closure in this case.

We consider the edge formulation of the stable set problem. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived from one row of the simplex tableau as fractional Gomory cuts. It follows that the split closure is not stronger than the Chvatal closure for the edge relaxation of the stable set problem.

O número cromático fracionário χF(G) de um grafo G é um conhecido limite inferior para seu número cromático χ(G). Experimentos relatados na literatura mostram que usar χF(G), em lugar do tamanho da clique máxima, pode ser muito mais eficiente para orientar a busca em um algoritmo tipo branch-and-bound para determinação de χ(G). Uma dificuldade, porém, é tratar o modelo linear conhecido para χF(G), o qual apresenta um número exponencial de variáveis e demanda um caro processo de geração de colunas. Neste trabalho, examinamos uma formulação alternativa para obter um limite inferior para χF(G) que possui um número de variáveis linear no tamanho do grafo, porém um número exponencial de restrições. Utilizamos o método de planos-de-corte para lidar com esse inconveniente. Algumas heurísticas de separação são propostas, e experimentos computacionais mostram que valores muito próximos de χF(G), em muitos casos iguais, são encontrados em tempo inferior à implementação com geração de colunas.The fractional chromatic number χF(G) of a graph G is a well-known lower bound for its chromatic number χ(G). Experiments reported in the literature show that using χF(G), instead of the size of the maximum clique, can be much more efficient to drive a search in a branch-and-bound algorithm for finding χ(G). One difficulty though is to deal with the linear program that is known for χF(G). Such a formulation has an exponential number of variables and demands an expensive column generation process. In this work, we investigate the use of an alternative formulation to find a lower bound for χF(G), which has a linear number of variables but an exponential number of constraints. We use a cutting plane method to deal with this inconvenience. Some separation heuristics are proposed, and some computational experiments were carried out. They show that values very close to χF(G) (in many cases exact values) are found in less time than that required by the column generation.

In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality conditions are derived. They are based on the notion of equilibrium point of an exact penalization for LBP. It is described how an equilibrium point can be obtained with the simplex method. It is shown that the information in the simplex tableaux can be used to get necessary and sufficient local optimality conditions for LBP. Based on these conditions, a simplex type algorithm is proposed, which attains a local solution of LBP by moving in equilibrium points. A numerical example illustrates how the algorithm works. Some computational results are reported.

In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality in LBP is studied via two related problems (P) and P(M). Problem (P) is a one-level model obtained by replacing the innermost problem of LBP by its KKT conditions. Problem P(M) is a penalization of the complementarity constraints of (P) with a penalty parameter M. Characterizations of a (strict) local solution of LBP are derived. In particular, the concept of equilibrium point of P(M) is used to characterize the local optima of (P) and LBP.

The capacitated plant location problem with linear transportation costs is considered. Exact rules and heuristics are presented for opening or closing of facilities. A heuristic algorithm based on ADD/DROP strategies is proposed. Procedures are implemented with the help of lower and upper bounds using Lagrangean relaxation. Computational results are presented and comparisons with other algorithms are made.O problema de localização de facilidades capacitado com custos de transporte lineares é considerado. Testes exatos e heurísticas para abrir ou fechar facilidades são apresentados. Um algoritmo heurístico baseado em estratégias ADD/DROP é proposto. Os procedimentos são implementados com o auxílio de limites inferiores e superiores provenientes de relaxação lagrangeana. Resultados computacionais são apresentados e comparações realizadas com outros algoritmos.

We analyze two global algorithms for solving the linear bilevel program (LBP) problem. The first one is a recent algorithm built on a new concept of equilibrium point and a modified version of the outer approximation method. The second one is an efficient branch-and-bound algorithm known in the literature. Based on computational results we propose some modifications in both algorithms to improve their computational performance. A significant number of experiments is carried out and a comparative study with the algorithms is presented. The modified procedures has better performance than the original versions.

Certain subgraphs of a given graph G restrict the minimum number χ(G) of colors that can be assigned to the vertices of G such that the endpoints of all edges receive distinct colors. Some of such subgraphs are related to the celebrated Strong Perfect Graph Theorem, as it implies that every graph G contains a clique of size χ(G), or an odd hole or an odd anti-hole as an induced subgraph. In this paper, we investigate the impact of induced maximal cliques, odd holes and odd anti-holes on the polytope associated with a new 0-1 integer programming formulation of the graph coloring problem. We show that they induce classes of facet defining inequalities.

Abstract The capacitated plant location problem with linear transportation costs is considered. An algorithm based on ADD/DROP procedures is proposed. Exact rules are presented allowing an a priori opening or closing of facilities. Facilities left are submitted to an extension of the exact rules. Procedures are implemented with the help of lower and upper bounds using Lagrangean relaxation. Computational results are presented and comparisons with other algorithms are made.

Abstract The multiprocessor scheduling problem with precedence relations and unit costs is considered. New ILP formulations are proposed for the case where the number of processors is bounded. These are the first formulations with O(n2) variables and constraints.

We analyze the article “A modified simplex approach for solving bilevel linear programming problems” (EJOR, 67, 126–135). We point out some problems in its theoretical analysis. Moreover, the algorithm proposed may not find a global solution as it is claimed. We give some examples in order to illustrate these remarks.

This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting. The answer is a nonconvex region that can be obtained as a finite union of convex polyhedra. We then establish a necessary and sufficient condition for the uniqueness of the lifting function., Comment: A subset of these results appeared in Proceedings of IPCO 2010, LNCS 6080, 2010, pp. 85--95

Given a graph with an arbitrary vertex coloring, the Convex Recoloring Problem (CR) consists of recoloring the minimum number of vertices so that each color induces a connected subgraph. We focus on the complexity and inapproximabiliy of this problem on k-colored graphs, for fixed k ≥ 2. We prove a very strong complexity result showing that CR is already NP-hard on k-colored grids, and therefore also on planar graphs with maximum degree 4. For each k ≥ 2, we also prove that, for a positive constant c, there is no cln n-approximation algorithm even for k-colored n-vertex bipartite graphs, unless P = NP. For 2-colored (q,q − 4)-graphs, a class that includes cographs and P 4-sparse graphs, we present polynomial-time algorithms for fixed q. The same complexity results are obtained for a relaxation of CR, where only one fixed color is required to induce a connected subgraph.

This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting. The answer is a nonconvex region that can be obtained as the union of convex polyhedra.

The cooperation between the Mathematical Programming (MP) and Constraint Programming (CP) paradigms has come to focus in the recent years. The impossibility of solving bigger instances alone and the apparently complementarity between the two approaches pushes towards further researches on hybrid methods. We can define a linear binary optimization problem as (P) { min c.x: Ax≤ b, xi¾? Bn}, where xis a binary variable, Ai¾? Rm×nis the constraint matrix, bi¾? Rmis the right-hand side vector and ci¾? Rnis the objective function.