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

learn more… | top users | synonyms

13
votes
1answer
145 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
93 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 ...
0
votes
0answers
62 views

Using a corner-polyhedra-characterization to proof a connection of edges <-> base solutions

For polyhedra $P = \{x \in \mathbb{R}^n \mid Ax \leq b \}$, which I want to call type-I-polyhedra (as the inequality constraint in its definition is a type I-inequality), we have a ...
1
vote
0answers
261 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
534 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
113 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
152 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
174 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
897 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
532 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
447 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
91 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
280 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
149 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
411 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
74 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
594 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
344 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)
0
votes
0answers
51 views

computing centerpoint using linear programming

I was redirected from math.stackoverflow. So I am trying to teach myself discrete geometry and have started with the centerpoint problem. Could someone please help me understand computing ...
1
vote
1answer
715 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 ...
0
votes
0answers
327 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $F(x)$ $F(x) = \sum_{i=1}^{M}||x_{i+1} - x_i - K(\frac{x_{i+1} + x_i}{2})||^2 + ||x_1-c_1||^2 + ||x_N-c_2||^2$ , where $x$ is a vector of $N$ scalars, $c$ are ...
1
vote
2answers
594 views

Sign restriction on the Lagrange multiplier? Why?

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...
0
votes
1answer
60 views

primal simplex procedure

Minimize $-2x_1-x_2+2x_3$ subject to $x_1 +x_3 = 4$, $-2x_1 +x_2 = 8$ s.t. $x_1,x_2,x_3\geq 0$. In my book, the augmented matrix is defined as $[A : 0 : b; -c^T : 1 :0]$ (where : separates ...
0
votes
0answers
72 views

Solving PSD matrix in Newton's method

I have functions defined as follows: $f_1(A) = \sum\|x_i-x_j\|_A = \sum\sqrt{(x_i-x_j)^TA(x_i-x_j)}$ and $f_2(A) = \sum\|x_k-x_l\|^2_A$ where $A$ is a positive semi-definite (PSD) matrix, $x$ are ...
0
votes
1answer
69 views

Chaotic solutions to mixed integer linear problems

Is there a way to get the branch and bound algorithm to converge to a solution "close" to an initial value? One way I can think of, is to adding a "distance from initial value" term to the cost ...
0
votes
1answer
45 views

How do I solve a LP problem when constrains have different inequalties?

How can I solve this LP problem: Maximize p=x subject to : x+y <=30 x-2y <= 0 2x+y >=30 x>=0 , y>=0 using simplex method?
1
vote
1answer
408 views

Convex hull of sets defined by (in)equalities

If you define the convex hull of a set $X$ as the set of all convex combinations of elements of $X$, it becomes difficult to decide if a given element $w$ belongs or not to $conv(X)$ (You have to ...
0
votes
2answers
694 views

Gradient solver

my question is about gradient algorithms. Lets have function f like: $f(x) = \|Ax-b\|^2$ and i want to find its minimum (according to x). So i can use some gradient method, for instance gradient ...
1
vote
1answer
46 views

Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s?

Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s? When $a_i$'s are independent, it should easy. What ...
1
vote
1answer
143 views

Techniques for (upper-)bounding LP maximization

I have a huge maximization linear program (variables grow as a factorial of a parameter). I would like to bound the objective function from above. I know that looking at the dual bounds the objective ...
0
votes
1answer
143 views

trying to read quadratic programming problem in cplex, get error

I am trying to load a CPLEX LP file in to CPLEX using the "read" command. I believe that in this problem, I have a set of constraints that are quadratic. But, from what I understand CPLEX will still ...
-1
votes
1answer
251 views

How to express $y = x\ \mathrm{mod}\ 2$ as an ILP?

Using the signed modulo operation: $(x\ \mathrm{mod}\ 2) = \begin{cases} 0\ \mathrm{if}\ x\ \mathrm{is\ even} \\ 1\ \mathrm{if}\ x > 0\ \mathrm{and}\ x\ \mathrm{is\ odd} \\ -1\ \mathrm{if}\ x ...
1
vote
1answer
159 views

Continuity of a Parametric Linear Program

Consider the convex optimization problem $$ \min_{x \in X, \ y \in Y } x $$ $$ \text{sub. to } \ x A + B y + C = 0 $$ where $X = [0,1] \subset \mathbb{R}$, $Y \subset \mathbb{R}^M $ are compact ...
1
vote
1answer
269 views

Does the triangle inequality suffice to prove all minimum results on sums of absolute values of affine functions?

The title says it all ... more formally : let $n \geq 1$, and let $a_1, a_2 , \ldots ,a_n$ be positive numbers, let $b_1, b_2 , \ldots ,b_n$ be real numbers. Consider for $x\in {\mathbb R}$, $$ ...
0
votes
1answer
176 views

creating a set in ZIMPL (which creates .LP for SoPlex & CPLEX)

I am looking for some help creating a set dynamically in ZIMPL. I have a parameter table: ...
0
votes
1answer
183 views

Solving linear programming problem with global opt method

why not solve a linear programming problem with a global opt method, or a local search method as SQP or Newton methods? I am writting a solver facing linear and non linear problems, and I wonder ...
1
vote
1answer
132 views

Optimization for large scale linear problem with equality constraint

Given the wide range of optimization methods, which is the appropriate method to use? I am thinking of using either linear programming (interior-point methods) or augmented Lagrangian methods. Which ...
0
votes
1answer
168 views

Linear Programming Duality (Basic optimization)

Suppose that $A$ is an $m\times n$ matrix, $D$ is a $p\times n$ matrix, $b$ is an $m$-vector, and $d$ is a $p$-vector. Prove that there does not exist $n$-vector $x$ satisfying $$Ax \geq b, Dx \leq ...
3
votes
1answer
172 views

Efficiently solving a special integer linear programming with simple structure and known feasible solution

Consider an ILP of the following form: Minimize $\sum_{k=1}^N s_i$ where $\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of ...
1
vote
2answers
309 views

Need help with a Linear Programming homework.

Please help with the problem: A polyhedron P in $R^n$ is given by the system of m linear inequalities (of n variables). Furthermore, let P have k vertices (that is, k vectors satisfying all m ...
1
vote
1answer
83 views

Casting a linear (in)equality into a linear program problem

Suppose I have the systems $$S_1: Ax \leq b$$ where $A \in \mathbb{R}^{n\times m}$, $x \in \mathbb{R}^m$ and $b \in \mathbb{R}^n$, and $$S_2 : y^{\intercal}A=0,\\ y \geq 0,\\ y^{\intercal}b < 0 $$ ...
2
votes
0answers
120 views

Linear optimization, homework problem.

Please help with the following problem: Given a $m$ x $n$ matrix $A$, $m$-vectors $b$ and $y$, and $n$-vectors $c$ and $x$. Write the dual $LP$ problems $P$ and $P^d$ in the standard form. Whether ...
2
votes
0answers
161 views

Linear optimization problem.

I have copied the entire problem from the book. It has 7 parts. Please show me how to do any 1-2 of the parts. I mostly understand the problem, but need to see a fully woked out problem. Given a $m$ ...
1
vote
2answers
141 views

Solving LP from tableau

$$\begin{array}{cccccc} & x1 & x2 & x3 & x4& x5 \\ -4& 2 & 0& -2 & 0& 3\\ 3 & 1 & 0 & -1& 1 & 3\\ 2 ...