MILP inheritently non convex MIP (implement mixed integer programming) more challenging is how to capture non-convexity, sometimes with non-linear data.

http://www.ie.boun.edu.tr/~taskin/pdf/IP_tutorial.pdf
inheritently non convex


https://theses.lib.vt.edu/theses/available/etd-04242006-114526/unrestricted/dissertation.pdf

manifold
http://acl.mit.edu/milp/MILP_for_Control.pdf


A Tutorial Guide to Mixed-Integer Programming Models and Solution Techniques J. Cole Smith and Z. Caner Ta¸skın Department of Industrial and Systems Engineering University of Florida Gainesville, FL 32611 cole@ise.ufl.edu, taskin@ufl.edu March 26, 2007 Abstract Mixed-integer programming theory provides a mechanism for optimizing decisions that take place in complex systems, including those encountered in biology and medicine. This chapter is intended for researchers and practitioners wanting an introduction to the field of mixed-integer programming. We begin by discussing basic mixed-integer programming formulation principles and tricks, especially with regards to the use of binary variables to form logical statements. We then discuss two core techniques, branchand-bound and cutting-plane algorithms, used to solve mixed-integer programs. We illustrate the use of mixed-integer programming in the context of several medical applications, and close with a featured study on Intensity Modulated Radiation Therapy planning


A Tutorial Guide to Mixed-Integer Programming Models and Solution Techniques J. Cole Smith and Z. Caner Ta¸skın Department of Industrial and Systems Engineering University of Florida Gainesville, FL 32611 cole@ise.ufl.edu, taskin@ufl.edu March 26, 2007 Abstract Mixed-integer programming theory provides a mechanism for optimizing decisions that take place in complex systems, including those encountered in biology and medicine. This chapter is intended for researchers and practitioners wanting an introduction to the field of mixed-integer programming. We begin by discussing basic mixed-integer programming formulation principles and tricks, especially with regards to the use of binary variables to form logical statements. We then discuss two core techniques, branchand-bound and cutting-plane algorithms, used to solve mixed-integer programs. We illustrate the use of mixed-integer programming in the context of several medical applications, and close with a featured study on Intensity Modulated Radiation Therapy planning. 1 Introduction This chapter describes the use of mixed-integer programming in optimizing complex systems, such as those arising in biology, medicine, transportation, telecommunications, sports, and national security. Consider, for instance, an emergency that results in 100 injuries. A triage center is established to administer first aid and assign victims to one of three nearby hospitals, each of which is capable of handling a limited number of patients. Each hospital may have varying equipment and staff levels, and each will be located at a different distance from the emergency. The optimization problem that arises is to assign patients to hospitals in a way that maximizes the effectiveness of care that can be given to the victims, while obeying physical capacity restrictions imposed by the hospitals. Experts often attempt to solve these problems based on intuition and experience, but the resulting solution is almost invariably suboptimal due to the inherent complexities of such problems. In applications of critical importance, there is sufficient motivation to turn to mathematical techniques that can provably obtain a “best” solution. 1 Mixed-integer programming is a subset of the broader field of mathematical programming. Mathematical programming formulations include a set of variables, which represent actions that can be taken in the system being modelled. One then attempts to optimize (either in the minimization or maximization sense) a function of these variables, which maps each possible set of decisions into a single score that assesses the quality of the solution. These scores are often in units of currency representing total cost incurred or revenue gained. The limitations of the system are included as a set of constraints, which are usually stated by restricting functions of the decision variables to be equal to, not more than, or not less than, a certain numerical value. Another type of constraint can simply restrict the set of values to which a variable might be assigned. Several applications involve decisions that are discrete (e.g., to which hospital an emergency patient should be assigned), while some other decisions are continuous in nature (e.g., determining the dosage of fluids to be administered to a patient). On the surface, the ability to enumerate all possible values that a discrete decision can take seems appealing; however, in most applications, the discrete variables are interrelated, requiring an enumeration of all combinations of values that the entire set of discrete variables can take. What are the implications of complete enumeration techniques on processing time? Suppose that there exist n variables, each of which can take on a value of zero or one. Furthermore, suppose that each configuration of these variables can be evaluated (tested for feasibility to the problem constraints and scored) using n computer operations. Since there are 2 choices for each variable, there are 2n configurations. Even if we are using a computer capable of processing 10 trillion operations per second (or 10 teraflops, and at the time of this writing, only 58 of the world’s top 500 supercomputers are capable of such a feat), if n = 50, the computer will take 1.5 hours to finish enumerating all possibilities. One might be tempted to simply let the computer run all night if need be for important problems, and while this is indeed valid for the case in which n = 50, the computational growth rate for these problems is astounding: for n = 60, the computer will require 80 days to terminate, and for n = 70, the computer will require 262 years. Another question regards the evolution of computing speed, noting that faster computers are constantly emerging. If the program must be finished within two hours, the current 10 teraflop machine will permit the solution of problems with n = 50. If a quantum leap is discovered that results in the invention of 10,000 teraflop machine, this fictional computer would only be able to handle problems with n = 60 within two hours. Computer speedups, however impressive, are simply no match for exponential enumeration problems. Therefore, a more efficient technique is required to solve problems containing discrete variables. Mixed-integer programming techniques do not explicitly examine every possible combination of discrete solutions, but instead examine a subset of possible solutions, and use optimization theory to prove that no other solution can be better than the best one found. This type of technique is referred to as implicit enumeration.