I think your definition of Integer programming is not correct. Integer programming or Mixed Integer Programming assumes that the solution has the all or some variables, integers. Most of the Integer programming models are usually using binary variable to indicate decisions.
Further, I think you tried to describe Linear programming in the beginning of your post. But Linear programming searches the vertices of the polytope and not the edges.
The biggest issue with Integer programming is the lack of convexity of the solution space when compared to Linear programming. So the approach for solving them is very different compared to Linear programming. If I made any mistakes in my post, I welcome to be corrected.
Constraint programming can be viewed as looking for feasible solutions to optimization problems.
So, what is optimization? For positive integers m and n, the real numbers R, and functions
f: R^n --> R
g: R^n --> R^m
find x in R^n to (problem MP1)
maximize f(x)
subject to
g(x) <= 0
where g(x) is regarded as an m x 1 matrix
and the 0 is also m x 1 but with all its components 0.
The constraints are the
g(x) <= 0
We say that we have m constraints.
The subject is essentially the same
using
g(x) >= 0
or
g(x) = 0
instead or minimizing instead of
maximizing.
Point x in R^n is feasible provided
it satisfies the constraints, that is,
g(x) <= 0
The feasible region is the set
F of all feasible x.
A point x is optimal if it is
feasible and makes f(x) as large
as possible. That is, x is
optimal provided for any feasible
y we have f(x) >= f(y).
If one or more of the functions
f or g is non-linear, then we
have non-linear programming.
Here we may use the Kuhn-Tucker
conditions to seek a point
that satisfies necessary conditions
for optimality. For an algorithm,
we may take gradients of the
constraints to set up a linear
program, solve that, do a line search,
and try again.
If functions f and g are linear, easily written using matrix algebra, then the optimization problem is linear programming (here programming is used in the British sense of operational planning).
Function f is convex provided for
any x, y in R^n and any t in [0, 1]
we have
t f(x) + (1 - t) f(y) >= f( t x + (1 - t) y )
That is, in a graph of f, a straight line
between (x, f(x) and (y, f(y) ) is on or
over the graph and never under the
graph. So, the straight line over
approximates the function.
If f is convex, then it is continuous (proof is not very difficult but is in Fleming, Functions of Several Variables). IIRC convex implies differentiable almost everywhere (maybe proof in R. T. Rockafellar, Convex Analysis). The epigraph is the graph of f and everything above it, and it is a convex set so has supporting hyperplanes and is the intersection of all the closed half spaces from its supporting (tangent) hyperplanes (IIRC, proof in Fleming). Such a
supporting hyperplane is called a
subgradient and can be quite useful
in optimization, e.g., Lagrangian
relaxation. There is a closely related,
really nice result in Hilbert space: Every
non-empty, closed convex subset has a unique
element of minimum norm. That can
be very nice to know!
To be more clear, a convex function, while
continuous, need not be differentiable.
Why not? Intuitively, at a point, the
function makes a sharp turn. Similarly, a cube is a convex set but has 10 sharp
edges and 8 sharp points that have supporting (tangent) planes, but these planes are not unique. So, a subgradient at a point would be a gradient and a
tangent plane if at that point it was
the only tangent plane. So, intuitively,
a subgradient is nearly a tangent
plane.
Function f is concave provided
that -f is convex. If f is convex
and -f is convex, then f is linear --
so, intuitively, a function that
is convex (or concave)
is half of being linear.
We have some astoundingly
powerful methods for solving
linear programming problems.
A significant fraction of the
Nobel prizes in economics
have been from economic
models based on linear
programming.
Some special cases, e.g.,
least cost network flows,
maximum matchings,
are special cases with
even better results for the
algorithms.
If in MP1 function f is concave and
funtion g is
linear, then again we have some
good methods.
If in MP1 function f is quadratic
and concave and function g is
linear, then we have the problem
of Markowitz in investment
portfolio management and his
Nobel prize in economics.
If we are maximizing a
convex function subject to
linear constraints, then we
have, IIRC, a problem in NP-complete.
If in linear programming
we require in addition that some or all of the components
of x are required to be integers,
then we have some integer
constraints and a problem in
integer linear programming (ILP).
ILP was one of the earliest
problems shown to be in
NP-complete.
So, that's a nutshell version of optimization.
Can also extend to accommodating randomness and
doing much the same over time.
The over time part is control theory,
e.g., how to fly an airplane from one point
to another in least time -- there are books, e.g., by Athans and Falb. Mike Athans was long at MIT and Falb, at the Brown Division of Applied Mathematics. Control theory
had a flurry of interest in the space
program. There is an extension, differential game theory, which
is like how best for a missile to
chase an airplane where the airplane
is best trying to avoid the missile.
Typically in control theory and
differential game theory we look
for necessary conditions for
optimality which usually turn out
to be in terms of Lagrange
multipliers.
Optimization over
time with randomness is essentially
stochastic optimal control, and the
main technique is
a version of dynamic programming.
An early proponent was Richard
Bellman.
The Black-Scholes Nobel prize work in
option pricing is a relatively
simple case of stochastic optimal
control.
So, in terms of MP1, constraint programming is, say,
find x in R^n so that
g(x) <= 0
that is, just find a point in the feasible
region R.
An example might be, yesterday
killed 5000 hogs and hung and chilled
the results. Today cut the hogs
and put the pieces in boxes
in 18 wheel trucks, about 40,000
pounds of load per truck, for
delivery to customers about 900
miles away.
Have only three bays in the loading
dock. So, want to know the order
in which to load the trucks to
get them all loaded in time.
So, have a constraint satisfacation
problem and not really an optimization
problem.
Fundamentally, i.e., in the sense
of computational complexity,
finding a feasible
point is as difficult as finding
an optimal point.
So, really, fundamentally,
constraint programming
is no easier than optimization.
IIRC at one time SAP and ILOG
were interested in CPLEX as
means of solving constraint
satisfaction problems. So,
to solve a constraint satisfaction
problem, start with some
optimization software.
Unfortunately it's not a written statement ( you can imagine that nobody working at apple would publicly say a thing like that). And it's not a direct source either, so you can very well take that with a grain of salt.
Actually, I am still hoping that someone will contradict me by providing concrete example of apple software using core data though, because as i stated, i invested a lot in that technology for an important project.
I think a web based killer is very far away in the time line. I recently was trying to make a huge gird in Photoshop and my i7+10gbRAM computer was unable to handle it. I think very simple stuff like annotating and cropping/red-eye fix can be done but I think a web based photo editor will fail when huge performance is required.
Not sure what your exact setup was, but your graphics card might simply have run out of memory. Which would then have happened pretty much independently from the software you were using.
Completely unrelated and Sorry for derailing but isn't it cart before the horse? I mean the horse is always in front of the cart. I am not a native English speaker. Am i missing anything?
i'm guessing you are referring to the homeless aspect of my well being..
without sounding too much like an a hole: i was fine then too;
this was 8 years ago, i was traveling in france, i ran out of money but had a return flight, i landed in nyc with 40$ and i had a decision to make: do i call someone for some help or do i make it work?; i chose to make it work
when i was in india my understanding of poverty shifted dramatically, i even to this day say that the states are devoid of any poverty
the exploitation of individuals with less in the states seems hinged on flaws in our general system
i wanted to help both poverty of the world, and those disenchanted and alienated by the country that let me stay the longest without a visa.. my birthplace
but, i am really bad at helping other people,
what i am really good at is helping myself
institutionally or bureaucratically offering my services to provide aide often calls for me to perform tasks for goals that i already think are futile, or refuse to try new things due to established procedures and participant seniority and frustrate me to stop trying to help others,
and individual help is time and emotionally consuming, only helps a single individual ignoring others' suffering, and ultimately feels manipulative
but! if i become homeless, if i am without a place to live and without a cent to my name, i was confident i could crawl my way out of that caste, what i found was living in public spaces made sense under certain circumstances, the first time around i spent 4 months in new york's underbelly, then a year later i came back for another 4 because i knew how to play the game.. and i could play it really well
one thing i learned in my time living on the streets of many cities around the world, and meeting and living alongside many people doing the same was that homelessness is a choice
i know this is an unpopular sentiment.. the best of the worst rationalisations these days seems to be 'mental illness', people without a clue love to say 'homelessness is a mental illness issue', somehow people have convinced themselves that there is compassion in undermining other peoples' choices
now, to say 'it is a choice' is a pithy simplification of a vastly complex idea:
we need to determine what are bad choices both for individuals and for our collective happiness and comfort,
and how to interact with people making those bad choices
we need to determine why the choice is being made,
honestly a lot of the people i got to know or chose to avoid were just doing what they wanted to be doing and either our dominant society rejected them or they saw it as abhorrent and opted out of it: i need to do your work for you for a pittance of your benefiting off of said work in order to pay a monthly fee for a stronger box with a lock on it so i can collect things in it free of constant fear of it being taken from me when my guard is down? i think i'll just accept the consequences of living without employment then, those seem more manageable to me;
but i love being able to have a shower, it is really difficult to enjoy the rain when you are without a shower and dry clothes to go home to and i love to enjoy the rain
so that became my baseline: getting people jobs they already knew they were uninterested in having is ridiculous, but creating a culture where anyone can take a warm shower and get warm clothes when they are needed, now that is something.. so i dedicate my free time to dreaming up my favourite way to achieve this
o, and food, everyone needs food
food should be free..
"When can I go into the supermarket and buy what I need with my good looks?"(i)
food will be free in the future
> I have 20/11 vision with a mutation that causes me to see a lower-band of UV. It overstimulates my ocular processing and causes migraines. I wear amber glass eye glasses with +.02 diopiter lenses to help reduce this problem. Because of this, I have an absolute obsession and facination with purple objects.
I remember the original poster participated in the comment section but (sigh) I don't know how to get there.
Calling Stallman a jerk is definitely uncalled for. I personally think he is the epitome of everything that is right with the Computer Science. It is your prerogative to distribute the software however you like. Remember that Stallman created something which most of us can only sapire about.
They don’t, HBO is acutely aware of the motivations of pirated content, and even more aware of the challenges they’d face being a stand-alone provider. Not trying to single your comment out but I see this sentiment all the time with HBO. They’ve obviously done the math and concluded that at this point they make the most money by subscription fees to cable providers, DVD and Online sales, then they would - if they started offering every show for sale at the same time as air-date, likely diminishing their cable subscription fees.
It's huge risk mitigation. If they're a stand-alone provider, and one of their shows doesn't draw in the viewership it needs to, they immediately feel that.
But since they've got all this "free" money coming in through deals with various providers, there isn't an as immediate effect.
