A bisection method for the traveling salesman problem
A combinatorial arc tolerance analysis for network flow problems.
A Comparison of Algorithms for the Maximum Clique Problem
A derivation of Lovász’ theta via augmented Lagrange duality
A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to Poljak et al. [13], and further developed in Lemaréchal and Oustry [9], leads to simple alternative derivations of well-known, important relaxations to two well-known problems of discrete optimization: the maximum stable set problem and the maximum vertex cover problem. The resulting relaxation is easily transformed to the well-known Lovász number.
A Derivation of Lovász' Theta via Augmented Lagrange Duality
A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to Poljak et al. [13], and further developed in Lemaréchal and Oustry [9], leads to simple alternative derivations of well-known, important relaxations to two well-known problems of discrete optimization: the maximum stable set problem and the maximum vertex cover problem. The resulting relaxation is easily transformed to the well-known Lovász θ number.
A discrete-time approximation technique for the time-cost trade-off in PERT networks
We develop a discrete-time approximation technique dealing with the time-cost trade-off problem in PERT networks. It is assumed that the activity durations are independent random variables with generalized Erlang distributions, in which the mean duration of each activity is a non-increasing function of the amount of resource allocated to it. It is also assumed that the amount of resource allocated to each activity is controllable. Then, we construct an optimal control problem with three conflicting...
A dual algorithm for the minimal cost flow problem
A Dual Exterior Point Simplex Type Algorithm for the Minimum Cost Network Flow Problem
A dual feasible forest algorithm for the linear assignment problem
A generalization of the convex-hull-and-line traveling salesman problem.
A new formulation and solution of the sequencing problem: mathematical model
A new relaxation in conic form for the euclidean Steiner problem in
In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in . We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an -optimal solution for this latter problem using interior-point algorithm.
A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ
In this paper, we present a new mathematical programming formulation for the Euclidean Steiner Tree Problem (ESTP) in ℜ. We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ-optimal solution for this latter problem using interior-point algorithm.
A note on minimum-dummy-activities PERT networks
A note on some separable location problems - a multicriterial approach
A Note on Spanning Trees for Network Location Problems
A note on the Chvátal-rank of clique family inequalities
Clique family inequalities a∑v∈W xv + (a - 1)∈v∈W, xv ≤ aδ form an intriguing class of valid inequalities for the stable set polytopes of all graphs. We prove firstly that their Chvátal-rank is at most a, which provides an alternative proof for the validity of clique family inequalities, involving only standard rounding arguments. Secondly, we strengthen the upper bound further and discuss consequences regarding the Chvátal-rank of subclasses of claw-free graphs.
A Note on Two Problems in Connexion with Graphs.
A Parametric Visualization Software for the Assignment Problem
A problem of finding an acceptable variant in generalized project networks.