Talk:Candidate solution

About removing the stub template

Why this article is a stub? I do like it. I think that one of wikipedia's defects is that too many pages are too long, there are too many redundancies and overlapping information. The only thing that this article lacks is a reference section (unfortunately i can't find any reliable source in english). But i think this article is fairly complete. If no one replies to this post in some days, i'll remove the stub template.Jabbba (talk) 09:35, 8 February 2008 (UTC). Unfortuantely this not true for all situations

Additional definitions

I did not edit this article, but this page seems a useful place to add definitions for:

• nonfeasible problem — underlying problem proven to have no canditate solutions
• infeasible solution — solver unable to identify a candidate solution (timed out, for instance)

This terminology aligns with GLPK usage.

Robbiemorrison (talk) 06:10, 11 July 2010 (UTC)

Vocabulary

Is the vocabulary uniform here? I have heard different terms for what I believe are the same concepts, e.g. "admissible region"; "feasible solution" instead of "candidate", etc. This page should tell which is the most usual one (if there is one), and which terms are exactly equivalent or what are the differences. Also it might tell to which extent these terms also apply to integer linear programming or mixed problems.

I just did some quick searches, hopefully it helps a bit.

Google says the following: lp "feasible solution": 346 k hits; "Linear programming" "feasible solution": 282 k hits lp "admissible solution": 4 k hits; "Linear programming" "admissible solution": 4 k hits lp "candidate solution": 24 k hits; "Linear programming" "candidate solution": 27 k hits

Google Scholar, for "Linear programming" "feasible solution", gives a few well-cited articles that use the term "feasible solution" for what seems to be called in this article "candidate solution" (i.e. a solution which satisfies all constraints, not being necessarily optimal). E.g. "Convex programming with set-inclusive constraints and applications to inexact linear programming", AL Soyster - Operations research, 1973 - JSTOR (this is the most cited article given by Scholar to which I have access).

Scholar gives less citations and less results for "Linear programming" "candidate solution". I have unfortunately not access to many of these articles. One of the referenced articles, "A Branch and Bound Algorithm for the Knapsack Problem", Peter J. Kolesar, Management Science, 1967, http://www.jstor.org/stable/2628089, uses "feasible solution" to designate solutions, non necessarily optimal, that satisfy the constraints, including the integer constraints. They call "solution" or "loading" those solutions that satisfy only the subset of constraints not dealing with the integer restrictions. They use the term "candidate solution" only to designate a solution that is a candidate to be an optimal solution (the term is only used in p. 731).

"Linear programming" "admissible solution", on Google Scholar, has only 688 hits. I did not check the results.

In my current state of mind I would tend to think that the term "feasible solution" seems to be the usual term for what is currently called "candidate solution" in this article. It might be misleading for the reader, esp. considering that the latter term seems to be sometimes used for something different.

Could somebody check the definitions in some well known English textbooks? (I mostly have access to books written in French.) --OlivierMiR (talk) 15:09, 10 January 2012 (UTC)

One well-known textbook is Boyd/Vandenberghe: Convex optimization (available as pdf for free, see Optimization problem). In Section 4.1 Optimization problems, the authors define a point as feasible if it satisfies the constraints. A problem is said to be feasible if there exists at least one feasible point, and infeasible otherwise. The set of all feasible points is called the feasible set or constraint set. Assume the optimal value of the problem is p*. A point x* is optimal if it is feasible and f(x*)=p*. The set of all optimal points is called the optimal set.

The authors of this book use the term feasible point consistently (at least almost). Although the term feasible solution is common, it is a bit unfortunate since it mixes the two concepts feasible point and solution point. A feasible solution is feasible, but need not be a solution.

The terms candidate and candidate solution are used more sparingly and the meaning seems a bit more vague. On p. 302 for example, they talk about plausible candidates. Isheden (talk) 16:58, 10 January 2012 (UTC)

The same with candidate solution. It can be some approximation which doesn't satisfy constraints and only after several iterations become feasible solution. CLRS use term feasible. --Igor Yalovecky (talk) 16:37, 16 December 2014 (UTC)