The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Article Download View The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Alberto Del Pia
A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
Article Download View A polynomial-size extended formulation for the multilinear polytope of beta-acyclic hypergraphs
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
An SDP Relaxation for the Sparse Integer Least Square Problem
In this paper, we study the polynomial approximability or solvability of sparse integer least square problem (SILS), which is the NP-hard variant of the least square problem, where we only consider sparse {0, ±1}-vectors. We propose an l1-based SDP relaxation to SILS, and introduce a randomized algorithm for SILS based on the SDP relaxation. In … 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
On the Complexity of Separation From the Knapsack Polytope
We close three open problems in the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1,k)-configuration inequalities, and weight inequalities are all NP-complete. We also give a number of special cases where the separation problem can be solved in polynomial time. Article Download … Read more
Simple odd beta-cycle inequalities for binary polynomial optimization
We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd beta-cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle … Read more
Multi-cover Inequalities for Totally-Ordered Multiple Knapsack Sets
We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus, we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have … Read more
An Approximation Algorithm for Indefinite Mixed Integer Quadratic Programming
In this paper we give an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem. The algorithm runs in polynomial time if the rank of the quadratic function and the number of integer variables are fixed. The running time of the algorithm is expected unless P=NP. In order to design … Read more
Complexity, Exactness, and Rationality in Polynomial Optimization
We study representation of solutions and certificates to quadratic and cubic optimization problems. Specifically, we focus on minimizing a cubic function over a polyhedron and also minimizing a linear function over quadratic constraints. We show when there exist rational feasible solutions (and if we can detect them) and when we can prove feasibility of sublevel … Read more