1,721,354 research outputs found
Local branching
No full textThe availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box "tactical" tool to explore effectively suitable solution subspaces defined and controlled at a "strategic" level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. © 2003 Springer-Verlag
Experiments on virtual private network design with concave capacity costs
No full textFor the first time in the literature, this paper considers computational aspects of concave cost virtual private network design problems. It introduces careful bound tightening mechanisms and computationally demonstrates how such bound tightening could impressively improve convex relaxations of the problem. It turns out that, incorporating such bound tightening with a general solution approach could significantly enhance the behavior of the solution approach over the problem
A theoretical and computational equilibria analysis of a multi-player kidney exchange program
No full textA main aim of kidney exchange programs (KEPs) is to maximize the number of transplants within a pool of incompatible patient-donor pairs by exchanging donors. A KEP involving pairs from pools of several hospitals, regions, or countries has the potential to increase the number of transplants. These entities may behave strategically and strive to maximize the transplant benefit for their patients. Recently, a decentralized non-cooperative game was formulated to model this situation, and the game solutions (equilibria) for the 2-player case were characterized when each player's utility is the number of her patients receiving a kidney and exchanges are restricted to pairwise. In this paper, we generalize the result on the existence of social welfare equilibra for N-players and discuss the impact in the game solutions when transplant information quality is introduced, changing the players’ utilities. Furthermore, the game theory model is analyzed through computational experiments on instances generated by leveraging data of the Canadian Kidney Paired Donation Program. These experiments highlight the importance of using the concept of Nash equilibrium, as well as, the need of further research to assist policy makers once measures on transplant quality are available
On the knapsack closure of 0-1 integer linear programs
Full text linkMany inequalities for Mixed-Integer Linear Programs (MILPs) or pure Integer Linear Programs (ILPs) are derived from the Gomory corner relaxation, where all the nonbinding constraints at an optimal LP vertex are relaxed. Computational results show that the corner relaxation gives a good approximation of the integer hull for problems with general-integer variables, but the approximation is less satisfactory for problems with 0-1 variables only. A possible explanation is that, for 0-1 ILPs, even the non-binding variable bound constraints xj≥0 or xj≤1 play an important role, hence their relaxation produces weaker bounds.In this note we address a relaxation for 0-1 ILPs that explicitly takes all variable bound constraints into account. More specifically, we introduce the concept of knapsack closure as a tightening of the classical Chvátal-Gomory (CG) closure. The knapsack closure is obtained as follows: for all inequalities wTx≥w0 valid for the LP relaxation, add to the original system all the valid inequalities for the knapsack polytope conv{xε{0,1}n:wTx≥w0}. A MILP model for the corresponding separation problem is also introduced. © 2010 Elsevier B.V
On the integration of Tabu Search techniques in Constraint Programming
No full textIn a recent paper, Focacci, Laburthe and Lodi (2002) surveyed the integration between Local Search and Constraint Programming which seems to be suitable to address real-world combinatorial optimization problems. In this paper, we focus on the integration of the machinery developed in the Tabu Search context into incomplete global search algorithms based on CP. The main issue is to re-interpret the techniques developed within Tabu Search for complete solutions so as to apply them to internal nodes of a tree search, i.e., to partial solutions
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Disjunctive cuts in Mixed-Integer Conic Optimization
Full text linkThis paper studies disjunctive cutting planes in Mixed-Integer Conic Programming. Building on conic duality, we formulate a cut-generating conic program for separating disjunctive cuts, and investigate the impact of the normalization condition on its resolution. In particular, we show that a careful selection of normalization guarantees its solvability and conic strong duality. Then, we highlight the shortcomings of separating conic-infeasible points in an outer-approximation context, and propose conic extensions to the classical lifting and monoidal strengthening procedures. Finally, we assess the computational behavior of various normalization conditions in terms of gap closed, computing time and cut sparsity. In the process, we show that our approach is competitive with the internal lift-and-project cuts of a state-of-the-art solver
Joint location and pricing within a user-optimized environment
No full textIn the design of service facilities, whenever the behaviour of customers is impacted by queueing or congestion, the resulting equilibrium cannot be ignored by a firm that strives to maximize revenue within a competitive environment. In the present work, we address the problem faced by a firm that makes decisions with respect to location, service levels and prices and that takes explicitly into account user behaviour. This situation is modelled as a nonlinear mathematical program with equilibrium constraints that involves both discrete and continuous variables, and for which we propose an efficient algorithm based on an approximation that can be solved for its global optimum
On the Estimation of Discrete Choice Models to Capture Irrational Customer Behaviors
No full textThe random utility maximization model is by far the most adopted framework to estimate consumer choice behavior. However, behavioral economics has provided strong empirical evidence of irrational choice behaviors, such as halo effects, that are incompatible with this framework. Models belonging to the random utility maximization family may therefore not accurately capture such irrational behavior. Hence, more general choice models, overcoming such limitations, have been proposed. However, the flexibility of such models comes at the price of increased risk of overfitting. As such, estimating such models remains a challenge. In this work, we propose an estimation method for the recently proposed generalized stochastic preference choice model, which subsumes the family of random utility maximization models and is capable of capturing halo effects. In particular, we propose a column-generation method to gradually refine the discrete choice model based on partially ranked preference sequences. Extensive computational experiments indicate that our model, explicitly accounting for irrational preferences, can significantly boost the predictive accuracy on both synthetic and real-world data instances. Summary of Contribution: In this work, we propose an estimation method for the recently proposed generalized stochastic preference choice model, which subsumes the family of random utility maximization models and is capable of capturing halo effects. Specifically, we show how to use partially ranked preferences to efficiently model rational and irrational customer types from transaction data. Our estimation procedure is based on column generation, where relevant customer types are efficiently extracted by expanding a treelike data structure containing the customer behaviors. Furthermore, we propose a new dominance rule among customer types whose effect is to prioritize low orders of interactions among products. An extensive set of experiments assesses the predictive accuracy of the proposed approach by comparing it against rank-based methods with only rational preferences and with more general benchmarks from the literature. Our results show that accounting for irrational preferences can boost predictive accuracy by 12.5% on average when tested on a real-world data set from a large chain of grocery and drug stores. Copyright
- …
