Questions on linear programming, the optimization of a linear function subject to linear constraints.

learn more… | top users | synonyms

1
vote
1answer
821 views

Example of a quadratic programming problem with no optimal solution on vertices?

Is there a way to write a quadratic programming problem with two variables bounded, nonempty feasible region linear constraints and yet have none of the vertices of the region optimize the ...
2
votes
1answer
446 views

Developing Constraints for a linear programming based problem

Recently, I thought of developing a mathematical approach to a task I commonly do every week. Simply enough, it's a schedule. That said, I have a few questions regarding the process. I haven't ...
0
votes
1answer
19 views

why the optimized point always appear in the interception in LP problem

As the topics, why the optimized point always appear in the interception in LP problem? I think there should be a proof but i am not sure about it.
3
votes
0answers
67 views

relation between solution of a linear program and its perturbation

I have a linear program over a finite set of points $(x_1, x_2,\ldots, x_m)\in\mathbb{R}^n$: $$ \max_j c' x_j $$ Suppose the solution of this LP is obtained at a point $x_{j_1}$, which is a vertex ...
0
votes
1answer
148 views

Parametric Linear Program: Continuous Solution?

Consider the parametric linear problem $$ x^*(\theta) := \min_{Y , \ Z } \left\| Z \right\|_1 $$ $$ \text{sub. to: } \ \theta A + B Y = \theta C Z.$$ where $Y \in \mathbb{R}^{m \times s} $, $Z \in ...
1
vote
1answer
86 views

Proof required for an alternate method in solving a linear programming problem

Suppose that P and Q are two of the corner points of the feasible region lying completely in the first quadrant. In addition, P is located at South-East of Q*. z = 0 (or more specifically, Ax + By = ...
1
vote
0answers
19 views

Use Exact Non-linear formulation or a linear approximation?

I am writing a paper that discusses results to solve stochastic problems with recourse analytically. The problem is nonlinear. I can also write an approximate stochastic linear program to sove the ...
5
votes
1answer
426 views

Minimal set of inequalities

I have a set of $m$ linear inequalities in $R^n$, of the form $$ A x \leq b $$ These are automatically generated from the specification of my problem. Many of them could be removed because they are ...
1
vote
0answers
307 views

linear programming

Suppose you have won \$ 6000 from OK Grand challenge promotion and you want to invest is. Upon hearing the news , your two differnt friends Mukanya and Mhofu offer you each an opportunity to become a ...
0
votes
1answer
53 views

Can standard Linear Programming algorithms return all valid solutions without losing their efficiency?

I have a (generalized) Linear Programming problem to solve. I anticipate exactly two equally valid optimizations of my objective function. I would be happy if I could receive both these points; it ...
0
votes
2answers
656 views

Need Homework Help: A small corportion borrowed $500,000, some at 9%, 10% and 12%. Use a system of equations--how much was borrowed at each rate if…

A small software corporation borrowed 500,000 cash to expand its software line. The corporation borrowed some of the money at 9%, some at 10%, and some at 12%. Use a system of equations to determine ...
0
votes
1answer
345 views

Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and..

Prove that an optimal solution $x^*$ of the problem 1 $\min f(x)$ s.t $x\in \mathbb{R}^n$ and an optimal solution $(\bar{x},\bar{z})$ of the problem 2 $\min z $ s.t $z\ge f(x)\,, x\in \mathbb{R}^n$ ...
2
votes
1answer
167 views

Maximizing a linear combination of certain integers

Consider some tuple $x = (x_1, ..., x_k) \in \mathbb{N}^k$ of $k$ non-negative integers such that $x_1 > x_1 > ... > x_k$ and suppose that $A \subset \mathbb{N}^k$ is such that there exists a ...
1
vote
3answers
451 views

Find a nonnegative basis of a matrix nullspace / kernel

I have a matrix $S$ and need to find a set of basis vectors $\{\mathbf{x_i}\}$ such that $S\mathbf{x_i}=0$ and $\mathbf{x_i} \ge \mathbf{0}$ (component-wise, i.e. $x_i^k \ge 0$). This problem comes ...
0
votes
1answer
400 views

LP: nonbasic solution made into basic solution, help me with this terminology

Related chat here, reading the Bertsimas book now on pages 50-51. By the way, I am gathering Linear-Programming -related studying material here, welcome to read a book and have coffee :) I cannot ...
1
vote
0answers
93 views

Linear Optimization Problem - Assign Objects to People

Say you have a 100x5 matrix of integers between -10 and 10, including zero. Each row represents an object; each column represents a person's ranking of the objects. Of the possible ranking values ...
2
votes
1answer
141 views

How relevant is mathematical optimization today?

That's it. That's all I'd love to know from you guys. Mathematical optimization, with the aid of today's software. Do you think it's still relevant in today's world?
0
votes
2answers
352 views

Reduced cost zero for the two-phase Simplex?

I cannot understand the line -12, -4, -5, 1, 1, -1, 0, 0, 0. Now the formula $\bf c - \bf A ^t \bf y$ when $c=0$ will result into the line. It is just many times a ...
1
vote
2answers
1k views

Optimality conditions and Directions in Simplex method

I am trying to understand the optimality conditions in Simplex -method, more in the chat here -- more precisely the terms such as "reduced cost" i.e. $\bar{c}_j=c_j-\bf{c}'_B \bf{B}^{-1} \bf{A}_j$ and ...
1
vote
1answer
74 views

Interactive Vizualizer of different Simplex -methods?

My book [1] around the pages 80-100 outlines the theories behind different simplex methods such as Naive-Simplex, Revised-SImplex, Full-tableau-Simplex, Dual Simplex, etc-simplex --. It is very dry ...
1
vote
0answers
65 views

Using duality to establish a relationship between in two-stage linear programming

I'm currently working on a problem that involves a two-stage linear program (LP). For simplicity, I refer to the LP in first stage as LP$_1$, and the LP in the second stage as LP$_2$. The relationship ...
1
vote
3answers
185 views

Integer combination

i want write a module to find the integer combination for a multi variable fomula. For example $8x + 9y \le 124$ The module will return all possible positive integer for $x$ and $y$.Eg. $x=2$, ...
0
votes
1answer
105 views

Solving an optimization problem involving reciprocals

I am trying to solve the following minimization problem, perhaps by getting it into a LP form: Let $u= [u_1, u_2, ...u_N]^T$ a column vector, and $v=[{1\over u_1}, {1 \over u_2}, ...{1 \over u_N}]^T$ ...
1
vote
1answer
870 views

Using max/min operators in linear programming.

I'm currently implementing a Markov Decision Process using the solver GLPK, I'm following the lecture by Vincent Conitzer, and there is a step I don't understand between the theoretical problem and ...
2
votes
1answer
314 views

Books on AI, programming, optimization

I'm studying math (just started) and I like programming as well (just started this too), is there a career or a branch of research including deep aspect of this two aspects? Is there someone among you ...
2
votes
1answer
645 views

Optimization with non-negativity and norm constraint

I am facing the following optimization problem: $$\min_x w^tx \\ s.t. ||x|| = 1, \forall i: x_i \geq 0 $$ where $w$ and $x$ are real valued vectors. How would I solve this? My background is not ...
13
votes
1answer
154 views

How low can the approval rating of a majority candidate be?

“Ostrogorski's paradox” describes a strange situation in which voters decide on candidates based on issues in platforms, but on each issue of the platform, the majority of voters disapprove of the ...
1
vote
0answers
24 views

Background of choosing standard for of a linear program as type III inequalities?

In linear programming where we seek to minimize $c^Tx \to \text{min}_{x\in P}!$ with respect to some inequality constraints, why do we choose $P$ in the form $Ax \leq b$, $x \geq 0$ as the ...
2
votes
0answers
96 views

How to get the initial ellipsoid in the ellipsoid method for solving optimization problem?

If what I assume is correct, assumption : for a maximization problem, we run a binary search over estimated values, starting with max estimated value, and narrow down to the feasible optimal value ...
1
vote
0answers
281 views

Question simplex method application criteria?

Can we apply simplex method if one or more equation are equal to zero. tell me full criteria my question example is as follows: Maximize: $z=135x+50y$, subject to: $$\begin{align} ...
1
vote
2answers
703 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
2
votes
0answers
119 views

Why is every nontrivial surface of a polyhedron an intersection of facets?

In the geometry of (convex) polyhedra used for linear optimization, one has the lemma: Consider the inequality $Ax \leq b$ where $A^+ x \leq b^+$ (the non-implicit inequalities of $Ax \leq b$) ...
1
vote
0answers
158 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
2
votes
0answers
82 views

Feasibility checking

I have a question regarding feasibility checking. I need to check whether the system $\{ x: Ax=b , x \geq 0 \}$ has a feasible solution. 1- What is the best worst case running time for this decision ...
1
vote
3answers
1k views

Percentages - Find Maximum value.

3 candidates A,B and C contest an election. A gets at least 40% of all the votes. B gets at least 20% of the number of votes that A gets and cannot get more than 80% of number of votes that c gets. ...
2
votes
1answer
203 views

LP unboundedness

Does there exist a way to check if a linear programming problem is unbounded without solving it directly? In other words, How the unboundedness of an LP can be realized from its structure. Assume the ...
1
vote
1answer
1k views

Strict inequalities in LP

How should we deal with strict inequalities in a linear programming problem? For example: inequalities such as $ax< b$;
6
votes
2answers
573 views

Solving geometric problems using Linear Programming

Is it possible to find an LP formulation to test whether $n$ points in the plane are in convex position?
1
vote
2answers
613 views

$\ell_0$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min:\|x\|_0$ subject to:$Ax=b$. $\|x\|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time has ...
1
vote
0answers
92 views

Simplex method with zero value constraints

The usual problem is to maximize some linear function $f(x_0, x_1 ... x_n)$ subject to linear constraints $g_i(x_0, x_1 ... x_n) \leq b_i$. My question is: What happens when all (or most) of the ...
1
vote
0answers
309 views

Book recommendation on Applied Integer Programming/Combinatorial Optimization/OR

Having some very basic and theoretical knowledge about these topics from my study, I'm looking for a book (or other good sources) that explains the stuff from a practical point of view. On the one ...
1
vote
1answer
159 views

Totally Uni-modular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
1
vote
1answer
2k views

Simplex: outgoing variable cannot re-enter the basis next iteration

How can I prove that in the simplex method, a variable that has just left the basis cannot re-enter the basis on the very next iteration? The pivoting rule is Dantzig's.
0
votes
1answer
441 views

Linear programming: the optimum of the shortest path problem is attained by $x \in [0, 1]^m$

Let $G=(V,E)$ be a graph, where $|E|=m$, and suppose we formulate the shortest path problem on $G$ as follows: minimize ${}^t(1,\dots,1)x$ such that $Bx={}^t(1,-1,0,\dots,0), x\in \{0,1\}^m$, where $B ...
0
votes
1answer
78 views

Solution for assigning independent tasks to independent individuals

I have $n$ tasks that I wish to delegate to $m$ independent individuals, where $m$ is a factor or divisor of $n$. Each of the tasks $T_{1} ... T_{n}$ is independent. From the following two extremes, ...
0
votes
0answers
75 views

A programming problem requiring mathematical optimization

This is a problem statement in one of the online Judges for programming. I am looking for an algorithm that gives optimized solution, not the best solution. I'm given a set of triplet of balls, each ...
1
vote
2answers
647 views

Minimizing Sum of Product

I'm given 3 multisets $A$, $B$, and $C$ each with $n$ elements. Now I'm to form $n$ (say $D_1$ to $D_n$) multisets of 3 elements each from $A$, $B$, and $C$, such that each of these $n$ multisets ...
2
votes
1answer
79 views

How can I fairly distribute identical goods bought at different prices amongst customers so that they all pay the same price?

I'm trying to allocate a product bought at different prices to different clients in a fair way. Initially, each of the $n$ client asked for a specific quantity of the product $a_1\ldots a_n$ The ...
0
votes
1answer
384 views

Totally Unimodular Matrices and Identity Matrices

I know that if a matrix $A$ is Totally Unimodular (TU), then the matrix $(A\; I)$ is unimodular. Can I then say that the matrix $(A\; -I)$ is also TU? ($I$ is the identity block matrix)
1
vote
1answer
883 views

Why does the “auxiliary problem” method work to find a feasible dictionary?

To quote my Linear Programming textbook, One way of getting around [the obstacles that arise when an LPP has an infeasible origin] uses a so-called auxiliary problem, $\min x_0$ subject to ...