We consider the problem of finding a shortest path in a directed graph with a quadratic objective function (the QSPP). We show that the QSPP cannot be approximated unless P=NP. For the case of a convex objective function, an n-approximation algorithm is presented, where n is the number of nodes in the graph, and APX-hardness … Read more
The floor layout problem (FLP) tasks a designer with positioning a collection of rectangular boxes on a fixed floor in such a way that minimizes total communication costs between the components. While several mixed integer programming (MIP) formulations for this problem have been developed, it remains extremely challenging from a computational perspective. This work takes … Read more
We present an approach to parallelize generation of feasible solutions of mixed integer linear programs in distributed memory high performance computing environments. The approach combines a parallel framework with feasibility pump (FP) as the rounding heuristic. The proposed approach runs multiple FP instances with different starting so- lutions concurrently, while allowing them to share information. … Read more
We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower’s traveling distance is longer … Read more
Facial reduction heuristics are developed in the interest of added performance and reliability in methods for mixed-integer conic optimization. Specifically, the process of branch-and-bound is shown to spawn subproblems for which the conic relaxations are difficult to solve, and the objective bounds of linear relaxations are arbitrarily weak. While facial reduction algorithms already exist to … Read more
We consider combinatorial optimization problems with uncertain objective functions. In the min-max-min robust optimization approach, a fixed number k of feasible solutions is computed such that the respective best of them is optimal in the worst case. The idea is to calculate a set of candidate solutions in a potentially expensive preprocessing and then select … Read more
In this paper, we extend a recently proposed scenario decomposition algorithm (Ahmed (2013)) for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the … Read more
Satisficing, as an approach to decision-making under uncertainty, aims at achieving solutions that satisfy the problem’s constraints as well as possible. Mathematical optimization problems that are related to this form of decision-making include the P-model of Charnes and Cooper (1963). In this paper, we propose a general framework of satisficing decision criteria, and show a … Read more
We present an online learning approach to variable branching in branch-and-bound for mixed-integer linear problems. Our approach consists in learning strong branching scores in an online fashion and in using them to take branching decisions. More specifically, numerical scores are used to rank the branching candidates. If, for a given variable, the learned approximation is … Read more
We consider a setting in which a company not only has a fleet of capacitated vehicles and drivers available to make deliveries, but may also use the services of occasional drivers who are willing to make a single delivery using their own vehicle in return for a small compensation if the delivery location is not … Read more