Presolve and statuses CPX_STAT_INForUNBD or IloCplex::InfOrUnbd.

When using mip solver , it is often to encounter cases where a specific optimization model is either infeasible or unbounded (CPX_STAT_INForUNBD in CPLEX).  Here is a nice post on this topic which provides insight on this flag message. 

http://www-01.ibm.com/support/docview.wss?uid=swg21399996

Automated Configuration of MIP solvers

Here is an interesting link about automating configuration  of MIP solvers

http://www.cs.ubc.ca/labs/beta/Projects/MIP-Config/

Generic Decomposition Algorithms for Integer Programs

Generic Decomposition Algorithm for Integer Programs is a research project conducted in Germany by Marco Lübbecke and Martin Bergner.

Here is the introduction of the project quoted from the website

There is no alternative to integer programming when it comes to computing proven quality or even optimal solutions to large-scale hard combinatorial optimization problems. In practical applications, matrices often have special structures exploitable in decomposition algorithms, in particular in brance-and-price. This opened the way to the solution of mixed integer programs (MIPs) of enormous size and complexity, both from industry and within mathematics, computer science, and operations research.
Yet, as the state-of-the-art, branch-and-price is implemented ad hoc for every new problem. Various frameworks are very helpful in this respect, still, this requires a solid expert knowledge. This project aims at making a significant contribution towards a generic implementation of decomposition algorithms. As a longterm vision, a MIP solver should be able to apply a decomposition algorithm without any user interaction. A precondition for such an automation is the answer to important algorithmic and theoretical questions, among them:

• recognition of decomposable structures in matrices and/or MIPs
• development of a theory (and appropriate algorithms) for evaluating the quality of a decomposition

In this project we address these questions. From a mathematical point of view, there are interesting relations to polyhedral combinatorics, graph theory, and linear algebra. A generic implementation of our findings is planned to be provided to the research community. To this end we closely cooperate with developers of MIP solvers (such as SCIP) and modeling languages (such as GAMS).

A primer in Column Generation

"A primer in Column Generation" is the first chapter of the book Column Generation, which is a good tutorial for Column Generation Techniques for solving integer linear programming problems. 

This paper is divided into four parts:

This first part provides an example to motivate the column generation, which is  shortest path problem with a time constraint. It provides detailed solution steps using column generation within the branch-and-bound framework.

The second part provides theoretical part and introduces the Dantzig-Wolfe Decomposition.

The third part  gives a dual point of view of the Dantzig-Wolfe Decomposition, which is the Lagrangian relaxation.

The fourth part actually hits a hot topic these days, how to exploit the matrix structure for diagonal blocks, which is the title of those days-"on finding a good formulation"

Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs

In the recent Operations Research, a paper titled  
Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs caught my attention.


The abstract of the paper is shown below
In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm that constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard notion of sequential cutting planes with ideas underlying the convex hull tree algorithm to help guide the choice of disjunctions to use within a cutting plane method. This algorithm, which we refer to as the cutting plane tree algorithm, is shown to converge to an integral optimal solution in finitely many iterations. Finally, we illustrate the proposed algorithm on three well-known examples in the literature that require an infinite number of elementary or split disjunctions in a rudimentary cutting plane algorithm.

comments on solving MIPs

Well, you know MIP solve times can be unpredictable, and sometimes it comes down to luck. Formulating good MIPs is something of a black art; and sometimes stupid things like the ordering of constraints can affect solve times. That said, there are a few tips that may help: 1) Introduce as many cuts and lazy constraints as you can, based on your knowledge of the problem. 2) When formulating MIP constraints, try to use formulations that give tight relaxations. For instance, avoid Big-M formulations when possible. If you have to use Big-M formulations, try to get tight value for the M. If you have no clue how to get a good value of M, formulate it as an indicator constraint, and CPLEX will try to find a good Big-M for you. 3) In some cases, you can formulate your problem as a Linear Generalized Disjunctive Program (LGDPs). LGDPs have a convex hull formulation, which are theoretically gives the tightest relaxations possible. The relaxations are usually either as good as, or better than those obtained from Big-M formulations. http://egon.cheme.cmu.edu/Papers/SawayaGrossmann.pdf The downside is that convex hull formulations require far more constraints than Big-M formulations, and sometimes this can make the problem more complex. The paper linked describes ways of introducing cutting planes to help speed up the convex hull formulations. Also, in some cases you can further tighten the problem by performing what is known as a "basic step". http://egon.cheme.cmu.edu/Papers/IMAGrossmannRuiz.pdf 4) There are other specific formulation tricks such as aggregation for problems with degenerate solutions, aggregation to break symmetry and so forth. All these require specific knowledge of the model. Right off the bat, you can usually get a small to significant speed-up if you use CPLEX >= 11's tuning feature, which can be invoked as follows. CPLEX will probe your problem and spit out some suggested cplex_options in the cplex.tune file. option cplex_options 'tunefile=cplex.tune tunedisplay=2 tunetime=1500'; This is also a good read: http://www-01.ibm.com/support/docview.wss?uid=swg21400023