ABSTRACT

One of the central trends in the optimization community over the past several years has been the steady improvement of general-purpose solvers. A logical next step in this evolution is to combine mixed integer linear programming, global optimization, and constraint programming in a single system. Recent research in the area of integrated problem solving suggests that the right combination of different technologies can simplify modeling and speed up computation substantially. In this paper we address this goal by presenting a general purpose solver that achieves low-level integration of solution techniques with a high-level modeling language. We validate our solver with computational experiments on problems in production planning, product configuration and machine scheduling. Our results indicate that an integrated approach reduces modeling effort, while solving two of the three problem classes substantially faster than state-of-the-art commercial software.

BIBTEX ENTRY

This paper was submitted in November 2005 and is currently under review. Check back later for the correct bibtex entry.

ABSTRACT

This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It settles the conjecture of Kouvelis and Yu and shows that the problem remains NP-complete even when the underlying graph is complete or when the cost intervals are all [0,1]. These results prove that the difficulty of RSTID stems from two distinct aspects: the topology of the graph and the numerical properties of the cost intervals. As a consequence, they suggest new directions for improving and evaluating existing search algorithms for this problem, since they have so far focused only on one of these aspects.

BIBTEX ENTRY

@Article{Aron:VanHentenryck:2004,
     author = {Ionu\c{t} D. Aron and Pascal Van Hentenryck},
     title = {On the complexity of the robust spanning tree problem with interval data},
     journal = {Operations Research Letters},
     volume = {32},
     issue = {1},
     pages = {36--40},
     month = {January},
     year = {2004} }

ABSTRACT

Wireless systems, and mobile ad hoc networks in particular, are more likely to experience transmission and routing errors than their wired counterpart. Factors like the lack of infrastructure, node mobility, and random radio link quality can contribute to significantly higher error rates in these networks. In addition, errors have a more serious impact on the network's resources, due to limitations in bandwidth and battery power inherent to the wireless ad hoc environment. This further complicates the task of designing scalable routing protocols, since larger networks are likely to experience even more errors, which may lead to slower convergence, longer end-to-end delay and unnacceptably high number of retransmissions. In this paper, we focus on the impact of error prevention and recovery on the scaling properties of on-demand protocols for ad hoc networks. Our analytical study, based on the evaluation of the Witness Aided Routing (WAR) and the Dynamic Source Routing (DSR) protocols, shows that the lack of localized intervention in handling errors translates eventually into lack of scalability, both in terms of performance and resource consumption. As route length increases, the performance of DSR degrades dramatically, especially in the presence of fluctuating wireless link quality. Even for small routes, DSR's lack of an error handling mechanism leads to very low probability of success when there is a non-zero probability that links are not bidirectional. On the other hand, WAR remains relatively insensitive both to the length of the route and to variations in mobility and call rates, and has a higher tolerance to radio link instability. This indicates that localized error correction can increase route effectiveness and alleviate the effects of short-lived radio link problems to an extent that allows the protocol to scale with the network size.

BIBTEX ENTRY

@article{Aron:Gupta:2001,
     author = {Ionu\c{t} D. Aron and Sandeep K. S. Gupta},
     title = {On the Scalability of On-Demand Routing Protocols for Mobile ad hoc Networks: An Analytical Study.},
     journal = {Journal of Interconnection Networks},
     volume = {2},
     number = {1},
     year = {2001},
     pages = {5-29},
     bibsource = {DBLP,
     http://dblp.uni-trier.de} }

ABSTRACT

We present a theoretical study on the idea of using mathematical programming relaxations for filtering binary constraint satisfaction problems. We introduce the consistent value polytope and give a linear programming description that is provably tighter than a recently studied formulation. We then provide an experimental study that shows that, despite the theoretical progress, in practice filtering based on mathematical programming relaxations continues to perform worse than standard arc-consistency algorithms for binary constraint satisfaction problems.

Keywords: cost-based filtering, hybrid methods, mathematical programming.

BIBTEX ENTRY

To appear (May 2006)

ABSTRACT

In recent years, the Constraint Programming (CP) and Operations Research (OR) communities have explored the advantages of combining CP and OR techniques to formulate and solve combinatorial optimization problems. These advantages include a more versatile modeling framework and the ability to combine complementary strengths of the two solution technologies. This research has reached a stage at which further development would benefit from a general-purpose modeling and solution system. We introduce here a system for integrated modeling and solution called SIMPL. Our approach is to view CP and OR techniques as special cases of a single method rather than as separate methods to be combined. This overarching method consists of an infer-relax-restrict cycle in which CP and OR techniques may interact at any stage. We describe the main features of SIMPL and illustrate its usage with examples.

BIBTEX ENTRY

@inproceedings{Aron:Hooker:Yunes:2004,
     author = {Ionu\c{t} D. Aron and John N. Hooker and Tallys H. Yunes},
     title = {SIMPL: A System for Integrating Optimization Techniques.},
     link = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3011{\&}spage=21},
     editor = {Jean-Charles R{\'e}gin and Michel Rueher},
     booktitle = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems,
     First International Conference,
     CPAIOR 2004,
     Nice,
     France,
     April 20-22,
     2004,
     Proceedings},
     publisher = {Springer},
     series = {Lecture Notes in Computer Science},
     volume = {3011},
     year = {2004},
     pages = {21-36},
     isbn = {3-540-21836-X},
     crossref = {DBLP:conf/cpaior/2004},
     bibsource = {DBLP,
     http://dblp.uni-trier.de} }

ABSTRACT

Robust optimization is one of the fundamental approaches to deal with uncertainty in combinatorial optimization. This paper considers the robust spanning tree problem with interval data, which arises in a variety of telecommunication applications. It proposes a constraint satisfaction approach using a combinatorial lower bound, a pruning component that removes infeasible and suboptimal edges, as well as a search strategy exploring the most uncertain edges first. The resulting algorithm is shown to produce very dramatic improvements over the mathematical programming approach of Yaman et al. and to enlarge considerably the class of problems amenable to effective solutions.

BIBTEX ENTRY

@Article{Aron:VanHentenryck:2002,
     author = {Ionu\c{t} D. Aron and Pascal Van Hentenryck},
     title = {A Constraint Satisfaction Approach to the Robust Spanning Tree Problem with Interval Data.},
     year = {2002},
     pages = {18-25},
     editor = {Adnan Darwiche and Nir Friedman},
     booktitle = {UAI '02,
     Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence,
     University of Alberta,
     Edmonton,
     Alberta,
     Canada,
     August 1-4,
     2002},
     publisher = {Morgan Kaufmann},
     isbn = {1-55860-897-4} crossref = {DBLP:conf/uai/2002},
     bibsource = {DBLP,
     http://dblp.uni-trier.de} }

ABSTRACT

In this paper we investigate the effect of local error recovery vs. end-to-end error recovery in reactive protocols. For this purpose, we analyze and compare the performance of two protocols: the Dynamic Source Routing protocol (DSR), which does end-to-end error recovery when a route fails and the Witness Aided Routing protocol (WAR), which uses local correction mechanisms to recover from route failures. We show that the performance of DSR degrades extremely fast as the route length increases (that is, DSR is not scalable), while WAR maintains both low latency and low resource consumption regardless of the route length.

BIBTEX ENTRY

@inproceedings{Aron:Gupta:2000,
     author = {Ionu\c{t} D. Aron and Sandeep K. S. Gupta},
     title = {Analytical comparison of local and end-to-end error recovery in reactive routing protocols for mobile ad hoc networks},
     booktitle = {MSWIM '00: Proceedings of the 3rd ACM international workshop on Modeling,
     analysis and simulation of wireless and mobile systems},
     year = {2000},
     isbn = {1-58113-304-9},
     pages = {69--76},
     location = {Boston,
     Massachusetts,
     United States},
     doi = {http://doi.acm.org/10.1145/346855.346866},
     publisher = {ACM Press},
     address = {New York,
     NY,
     USA},
    
}

ABSTRACT

Mobile ad-hoc networks may exhibit unidirectional links due to the nature of wireless communication. Presence of unidirectional links interferes with the control flow of many existing unicast routing protocols for such networks, which adversely affects their performance and limits their applicability. In this paper, we present a new protocol designed to support unicast routing over both bidirectional and unidirectional links in ad hoc networks, while preserving low bandwidth utilization and providing faster and more reliable packet delivery. The Winess Aided Routing (WAR) protocol is based on the concept of witness host, whose role is to help in bypassing a unidirectional or failed link along the path. We present a preliminary analysis to compare the expected performance of WAR with the Dynamic Source Routing (DSR) protocol.

BIBTEX ENTRY

@inproceedings{Aron:Gupta:1999,
     author = {Ionut D. Aron and Sandeep K. S. Gupta},
     title = {A Witness-Aided Routing Protocol for Mobile Ad-Hoc Networks with Unidirectional Links.},
     booktitle = {MDA},
     year = {1999},
     pages = {24-33},
     ee = {http://link.springer.de/link/service/series/0558/bibs/1748/17480024.htm},
     crossref = {DBLP:conf/mda/1999},
     bibsource = {DBLP,
     http://dblp.uni-trier.de} editor = {Hong Va Leong and Wang-Chien Lee and Bo Li and Li Yin},
     booktitle = {Mobile Data Access,
     First International Conference,
     MDA'99,
     Hong Kong,
     China,
     December 16-17,
     1999,
     Proceedings},
     publisher = {Springer},
     series = {Lecture Notes in Computer Science},
     volume = {1748},
     isbn = {3-540-66878-0},
     bibsource = {DBLP,
     http://dblp.uni-trier.de} }

ABSTRACT

***
*** Our ACM MSWiM paper was later copied almost in its entirety, renamed and submitted for publication without giving credit or citing our work, by some researchers we had nothing in common with. The rebranded paper appeared (under a different authorship and with minor changes and many obvious search-and-replace related mistakes) in IEEE Transactions on Computers , Vol. 52, No. 7, pp. 854-861, July 2003. Eventually, IEEE caught up and published this addendum in the July 2004 edition of the same journal. A copy of the renamed (IEEE) paper is available here. See how much of it you can match with our original work (and see if you can find the search-and-replace related mistakes in the IEEE paper - it should not be hard, since there are quite a few, although, surprisingly, they were not caught by any of the reviewers).

BIBTEX ENTRY

@journal{plagiarism,
     author = {Ramnath Duggirala and Rahul Gupta and Qing-An Zeng and Dharma P. Agrawal},
     title = {Performance Enhancements of Ad Hoc Networks with Localized Route Repair},
     journal = {IEEE Transactions on Computers},
     volume = {52},
     number = {7},
     pages = {854-861} month = {July} year = {2003} }