[Pyxl101]

While this may be true for linear programming, is it true for integer linear programming or binary integer programming, which one would presumably use to model Soduku? The Wikipedia article you posted claims that integer programming problems are NP-hard.

> If all of the unknown variables are required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NP-hard. 0-1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of Karp's 21 NP-complete problems.

Here is an article on the topic of "Binary and Mixed Integer Programming" which explains part of the Balas Additive Algorithm (infeasibility pruning, I believe) in terms of backtracking:

> At this point, both of the nodes just created are not eligible for further expansion, so we back up the tree, looking for a level at which one of the nodes is unexplored.

http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf

Another paper describes a method by Glover characterized as "A backtracking procedure for implicit enumeration".

> A particularization of the procedure based on Balas' algorithm. In S2 we presented and justified a flexible and economical back-tracking procedure for finding an optimal feasible solution of (P) by implicit enumeration.

See Figure 1 on page 182 (or page 6 in the PDF):

http://www.anderson.ucla.edu/faculty/art.geoffrion/home/docs...

This branch of mathematics is not my forte however, so if I've misunderstood then I'd appreciate clarification. It seems like the algorithm is not backtracking in the sense of generating possible solutions and checking them, but is backtracking in the sense of fathoming which next cheapest (partial) solution might be feasible, and abandoning it if proven to be definitely infeasible, in favor of examining the (then) next cheapest potential solution.

Finally, see the following paper that compares and contrasts Constraint Programming with Integer Programming, and characterizes both of them as instances of Tree Search:

http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...

[Pamar]

Extremely Coarse Approximation Alert

Try to imagine this: by manipulating an n-dimensional matrix in a certain way, you get, at each step, a result which is guaranteed to be part of your solution space. You also have a way to find out, at each step, if you have found the optimal solution (in terms of your objective function) or if no solution exists.

So the process goes like this: Put your constraints in the matrix.

  Loop -
    Manipulate Matrix
    Is this the optimal Solution?
      Yes - return solution
    Is the solution space empty/concave/unbound?
      Yes - return error
  End.

No backtracking in the sense of "try this... hmm... no, try this other".

I have used LP professionally in the past, and recently participated in the MOOC I linked above (as a refresher) but I might surely be missing something (the theory I studied at UNI too many years ago - now I just use it as a tool) or overgeneralizing too much. If anyone can provide corrections these will be welcomed.

[Pyxl101]

Could you clarify which algorithm you're referring to? Or name an example algorithm that works in the way you describe? What I find in academic literature seems to characterize Integer Programming as a search problem. See the following article that compares Constraint Programming with Integer Programming:

http://preserve.lehigh.edu/cgi/viewcontent.cgi?article=1780&...

> Since tree search is a basic solution technique employed in both constraint and integer programming, we begin with a generic overview of tree search as a technique for finding feasible solutions to mathematical models.

> Every tree search algorithm is defined by four elements: a node- processing procedure, pruning rules, branching rules, and search strategy. The processing step is applied at every node of the search tree beginning with the root node, and usually involves some attempt to further reduce the feasible set associated with the node by applying logical rules. [...]

> One particularly well-developed solution technique, called branch and bound, was introduced by Land and Doig. Branch and bound is frequently used to find solutions to integer programming problems; it is a tree search procedure in which a bound on the optimal value to each subproblem is obtained by solving a relaxation. In this thesis we assume the use of a linear programming relaxation in the branch and bound tree.

> The last piece of a branch and bound algorithm is a search strategy specifying the order in which to explore nodes of the tree. Depth-first search can be used to save memory in a branch and bound tree, since we must only remember the difference in solution between two successive nodes of the search tree.

Chapter nine of Applied Mathematical Programming from MIT classifies integer program solvers into three major groups:

http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf

> Whereas the simplex method is effective for solving linear programs, there is no single technique for solving integer programs. Instead, a number of procedures have been developed, and the performance of any particular technique appears to be highly problem-dependent. Methods to date can be classified broadly as following one of three approaches:

> i) enumeration techniques, including the branch-and-bound procedure;

> ii) cutting-plane techniques; and

> iii) group-theoretic techniques. [...]

> Branch-and-bound is essentially a strategy of ‘‘divide and conquer.’’ The idea is to partition the feasible region into more manageable subdivisions and then, if required, to further partition the subdivisions. In general, there are a number of ways to divide the feasible region, and as a consequence there are a number of branch-and-bound algorithms.

> An integer linear program is a linear program further constrained by the integrality restrictions. Thus, in a maximization problem, the value of the objective function, at the linear-program optimum, will always be an upper bound on the optimal integer-programming objective. In addition, any integer feasible point is always a lower bound on the optimal linear-program objective value. The idea of branch-and-bound is to utilize these observations to systematically subdivide the linear programming feasible region and make assessments of the integer-programming problem based upon these subdivisions.

The book describes the "cutting-plane" approach, which does seem to work more like how you're describing (a series of transformations), but also says:

> In practice, the branch-and-bound procedures almost always outperform the cutting-plane algorithm. Nevertheless, the algorithm has been important to the evolution of integer programming. Historically, it was the first algorithm developed for integer programming that could be proved to converge in a finite number of steps. In addition, even though the algorithm generally is considered to be very inefficient, it has provided insights into integer programming that have led to other, more efficient, algorithms.

[Pamar]

As I mentioned elsewhere, it has been ages since I took an actual formal exam on Linear Programming (and Integer Programming) - since then I always used dedicated sw to solve LP (there is for example a nice, self-contained LP solver in Numerical Recipes in C) and so I always focused more on how to describe the problems in terms of linear constraints.

"In my mind" it works like this: https://www.quora.com/What-is-the-difference-between-integer...

Having said this, while NP is guaranteed to terminate the actual computation time may take ages. Integer Programming may very well leverage the fact that the solution is restricted to integer values and apply different, faster algorithm to exploit this property - including search trees. But in the most general sense you do not need a search tree or backtracking for Linear Programming.