Strong valid inequalities for fluence map optimization problem under dose-volume restrictions

Fluence map optimization problems are commonly solved in intensity modulated radiation therapy (IMRT) planning. We show that, when subject to dose-volume restrictions, these problems are NP-hard and that the linear programming relaxation of their natural mixed integer programming formulation can be arbitrarily weak. We then derive strong valid inequalities for fluence map optimization problems under dose-volume restrictions using disjunctive programming theory and show that strengthening mixed integer programming formulations with these valid inequalities has significant computational benefits.     

Strong valid inequalities for Boolean logical pattern generation

0–1 multilinear programming (MP) captures the essence of pattern generation in logical analysis of data (LAD). This paper utilizes graph theoretic analysis of data to discover useful neighborhood properties among data for data reduction and multi-term linearization of the common constraint of an MP pattern generation model in a small number of stronger valid inequalities. This means that, with a systematic way to more efficiently generating Boolean logical patterns, LAD can be used for more effective analysis of data in practice. Mathematical properties and the utility of the new valid inequalities are illustrated on small examples and demonstrated through extensive experiments on 12 real-life data mining datasets.     

Valid inequalities for separable concave constraints with indicator variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

A least-distance programming procedure for minimization problems under linear constraints

In this paper, an algorithm is developed for solving a nonlinear programming problem with linear contraints. The algorithm performs two major computations. First, the search vector is determined by projecting the negative gradient of the objective function on a polyhedral set defined in terms of the gradients of the equality constraints and the near binding inequality constraints. This least-distance program is solved by Lemke's complementary pivoting algorithm after eliminating the equality constraints using Cholesky's factorization. The second major calculation determines a stepsize by first computing an estimate based on quadratic approximation of the function and then finalizing the stepsize using Armijo's inexact line search. It is shown that any accumulation point of the algorithm is a Kuhn-Tucker point. Furthermore, it is shown that, if an accumulation point satisfies the second-order sufficiency optimality conditions, then the whole sequence of iterates converges to that point. Computational testing of the algorithm is presented.     

Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints

A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.Research supported by National Science Foundation Grant ENG 76-12250     

Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems

In this paper, we are concerned with the linearly constrained global minimization of the sum of a concave function defined on ap-dimensional space and a linear function defined on aq-dimensional space, whereq may be much larger thanp. It is shown that a conical algorithm can be applied in a space of dimensionp + 1 that involves only linear programming subproblems in a space of dimensionp +q + 1. Some computational results are given.This research was accomplished while the second author was a Fellow of the Alexander von Humboldt Foundation, University of Trier, Trier, Germany.     

On convergence properties of a least-distance programming procedure for minimization problems under linear constraints

In Ref. 1, Bazaraa and Goode provided an algorithm for solving a nonlinear programming problem with linear constraints. In this paper, we show that this algorithm possesses good convergence properties.This paper was written under the guidance of Associate Professor C. Y. Wang. The author takes great pleasure in thanking him.     

Strong valid inequalities for orthogonal disjunctions and bilinear covering sets

In this paper, we derive a closed-form characterization of the convex hull of a generic nonlinear set, when this convex hull is completely determined by orthogonal restrictions of the original set. Although the tools used in this construction include disjunctive programming and convex extensions, our characterization does not introduce additional variables. We develop and apply a toolbox of results to check the technical assumptions under which this convexification tool can be employed. We demonstrate its applicability in integer programming by providing an alternate derivation of the split cut for mixed-integer polyhedral sets and finding the convex hull of certain mixed/pure-integer bilinear sets. We then extend the utility of the convexification tool to relaxing nonconvex inequalities, which are not naturally disjunctive, by providing sufficient conditions for establishing the convex extension property over the non-negative orthant. We illustrate the utility of this result by deriving the convex hull of a continuous bilinear covering set over the non-negative orthant. Although we illustrate our results primarily on bilinear covering sets, they also apply to more general polynomial covering sets for which they yield new tight relaxations.     

On the construction of test problems for concave minimization algorithms

We construct some classes of test problems of minimizing a concave or, more general, quasiconcave function over a polyhedral set. These test problems fulfil the general requirement that they have a global solution at a known point which is suitably chosen on the boundary of the feasible set.     

Metric regularity and second-order necessary optimality conditions for minimization problems under inclusion constraints

In this paper, we establish some general metric regularity results for multivalued functions on Banach spaces. Then, we apply them to derive second-order necessary optimality conditions for the problem of minimizing a functionf on the solution set of an inclusion 0F(x) withxC, whenF has a closed convex second-order derivative.The author is thankful to the referees for having helped him improve the quality of the paper.     

Sufficient conditions for solving linearly constrained separable concave global minimization problems

A concave function defined on a polytope may have many local minima (in fact every extreme point may be a local minimum). Sufficient conditions are given such that if they are satisfied at a point, this point is known to be a global minimum. It is only required to solve a single linear program to test whether the sufficient conditions are satisfied. This test has been incorporated into an earlier algorithm to give improved performance. Computational results presented show that these sufficient conditions are satisfied for certain types of problems and may substantially reduce the effort needed to find and recognize a global minimum.     

A numerical method for a class of continuous concave programming problems

The problem under consideration consists in maximizing a separable concave objective functional on a class of non-negative Lebesgue integrable functions satisfying a system of linear constraints. The problem is approximated by two sequences of concave separable programming problems with linear constraints. The convergence of the sequences of optimum values of these problems is investigated in the general case and the convergence of the sequences of optimum solutions in a special case. A numerical example is given.     

Strong formulations for mixed integer programs: valid inequalities and extended formulations

 We examine progress over the last fifteen years in finding strong valid inequalities and tight extended formulations for simple mixed integer sets lying both on the ``easy' and ``hard' sides of the complexity frontier. Most progress has been made in studying sets arising from knapsack and single node flow sets, and a variety of sets motivated by different lot-sizing models. We conclude by citing briefly some of the more intriguing new avenues of research. Received: January 15, 2003 / Accepted: April 10, 2003 Published online: May 28, 2003 Key words. mixed integer programming – strong valid inequalities – convex hull – extended formulations – single node flow sets – lot-sizing This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union.     

Exact penalty property for a class of inequality-constrained minimization problems

We use the penalty approach in order to study constrained minimization problems. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish the exact penalty property for a large class of inequality-constrained minimization problems.     

Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements

We consider the resource-constrained scheduling problem when each job’s resource requirements remain constant over its processing time. We study a time-indexed formulation of the problem, providing facet-defining inequalities for a projection of the resulting polyhedron that exploit the resource limitations inherent in the problem. Lifting procedures are then provided for obtaining strong valid inequalities for the original polyhedron. Computational results are presented to demonstrate the strength of these inequalities.     

Strong inequalities for capacitated survivable network design problems

We present several classes of facet-defining inequalities to strengthen polyhedra arising as subsystems of network design problems with survivability constraints. These problems typically involve assigning capacities to a network with multicommodity demands, such that after a vertex- or edge-deletion at least some prescribed fraction of each demand can be routed. Received: December 1997 / Accepted: April 2000?Published online September 20, 2000