Integer Factorization is in P
A polynomial-time algorithm for integer factorization, wherein integer factorization is reduced to solution of a convex polynomial-time integer maximization problem. Article Download View Integer Factorization is in P
Integer Programming
An Outer-Inner Approximation for separable MINLPs
A common structure in convex mixed-integer nonlinear programs is separable nonlinear functions. In the presence of such structures, we propose three improvements to the outer approximation algorithms. The first improvement is a simple extended formulation, the second is a refined outer approximation, and the third is a heuristic inner approximation of the feasible region. These … Read more
Approximating the solution for the multiparametric 0-1-mixed integer linear programming problem with interval data
In this paper we present algorithms to approximate the solution for the multiparametric 0-1-mixed integer linear programming problem relative to the objective function. We consider the uncertainty for the parameters that de fine the cost vector corresponding to a subset of 0-1-variables by assuming that each parameter belongs to a known interval. We suppose that we … Read more
On valid inequalities for quadratic programming with continuous variables and binary indicators
In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x’ and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which … Read more
A unified mixed-integer programming model for simultaneous fluence weight and aperture optimization in VMAT, Tomotherapy, and Cyberknife
In this paper, we propose and study a unified mixed-integer programming model that simultaneously optimizes fluence weights and multi-leaf collimator (MLC) apertures in the treatment planning optimization of VMAT, Tomotherapy, and CyberKnife. The contribution of our model is threefold: i. Our model optimizes the fluence and MLC apertures simultaneously for a given set of control … Read more
A family of polytopes in the 0/1-cube with Gomory-Chvátal rank at least ((1+1/6)n – 4)
We provide a family of polytopes P in [0, 1]^n whose Gomory-Chvátal rank is at least ((1 + 1/6)n – 4). Citation Rutcor 640 Bartholomew Road Piscataway, NJ 08854-8003 , July,2012 Article Download View A family of polytopes in the 0/1-cube with Gomory-Chvátal rank at least ((1+1/6)n – 4)
Mixed Integer Linear Programming Formulation Techniques
A wide range of problems can be modeled as Mixed Integer Linear Programming (MIP) problems using standard formulation techniques. However, in some cases the resulting MIP can be either too weak or too large to be effectively solved by state of the art solvers. In this survey we review advanced MIP formulation techniques that result … Read more
Polyhedral Aspects of Self-Avoiding Walks
In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this … Read more
Graver basis and proximity techniques for block-structured separable convex integer minimization problems
We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In previous work [R. Hemmecke, M. Koeppe, R. Weismantel, A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs, Proc. IPCO 2010, Lecture Notes in Computer Science, vol. 6080, Springer, 2010, pp. 219–229], … Read more
A new warmstarting strategy for the primal-dual column generation method
This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after … Read more