A Comparative Analysis on Combinatorial Optimization: Minlp Issues and Justification |

ABSTRACT:

Recently, the area of Mixed Integer Nonlinear Programming(MINLP) has experienced tremendous growth and a flourish of research activity.In this article we will give a brief overview of past developments in the MINLParena and discuss some of the future work that can foster the development ofMINLP in general and, in particular, robust solver technology for the practicalsolution of problems. Mixed-Integer Programs (MIP's) involving logicalimplications modeled through big-M coefficients, are notoriously among thehardest to solve. In this paper we propose and analyze computationally anautomatic problem reformulation of quite general applicability, aimed atremoving the model dependency on the big-M coefficients. Our solution schemedefines a master Integer LinearProblem (ILP) with no continuous variables, which contains combinatorialinformation on the feasible integer variable combinations that can be\distilled" from the original MIP model. The master solutions are sent toa slave Linear Program (LP), which validates them and possibly returnscombinatorial inequalities to be added to the current master ILP. Theinequalities are associated to minimal (or irreducible) infeasible subsystemsof a certain linear system, and can be separated efficiently in case the mastersolution is integer. The overall solution mechanism resembles closely theBenders' one, but the cuts we produce are purely combinatorial and do notdepend on the big-M values used in the MIP formulation. This produces an LPrelaxation of the master problem which can be considerably tighter than the oneassociated with original MIP formulation. Computational results on two specificclasses of hard-to-solve MIP's indicate the new method produces a reformulationwhich can be solved some orders of magnitude faster than the original MIPmodel. Numerous industrial problems can be modeled as MINLPproblems combining both numeric and integer variables. Several methods wereproposed to solve these problems. But industrial applications need more thansolving problems: dynamic problems, over-constrained problems, or explainingsolver behavior are features required by industrial applications.Explanation-based constraint programming offers such tools. In this paper, weshow how to apply explanation-based mechanisms for mixed problems thanks to ageneric framework. Last, some first experimental results are exposed: theoverhead due to explanation managing is acceptable and can even speed up someresolutions. In this work we deal with exponential sum models comingfrom data acquisition in the empirical sciences. We present a two step approachbased on Tikhonov regularization and combinatorial optimization, to obtainstable parameter estimations, which fit the data.