Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
6
votes
1answer
316 views

Difficulties in Writing the Dual of a Primal Program

I am a student and I am studying the following problem during my spare time. Your comments and suggestions would be helpful. Given the following primal program: (Decision variables are $\xi_{v}$, ...
6
votes
2answers
8k views

Understanding proof of Farkas Lemma

I've attached an image of my book (Theorem 4.4.1 is at the bottom of the image). I need help understanding what this book is saying. In the first sentence on p.113: "If (I) holds, then the primal ...
6
votes
2answers
176 views

Transform an optimisation problem into a linearly-constrained quadratic program?

I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
6
votes
1answer
348 views

Nearest signed permutation matrix to a given matrix $A$

Let $A \in \mathbb{R}^{n\times n}$ be a square matrix and let $Q \in O(n)$ be the nearest orthogonal matrix to $A$ under the Frobenius norm, i.e. $$Q = \text{arg}\min_{M \in O(n)} ||A - M||_{F}^2$$ ...
6
votes
1answer
115 views

Name for a cardinality-constrained transportation problem variant

The transportation problem is a well-studied problem in operations research. Given sources $i\in\{1, \ldots, n\}$ and destinations $j\in\{1, \ldots, m\}$, we seek to minimize the total cost of ...
6
votes
1answer
2k views

Computationally proving a linear programming solution is unique?

I have a simple linear programming problem min $c^{T}x$ subject to $Ax\leq b$. That gives me the solution I am looking for when solving in maple. My only problem is that I do not know how to check, ...
6
votes
1answer
1k views

Generating random linear programming problems

I've just finished writing a a linear programming problem solver which uses the simplex method. Now I would like to start optimizing my solver but before I can do this, I need a way of reliably ...
6
votes
1answer
1k views

How does multiplying a primal constraint by a constant change the dual solution?

Suppose we have the problem $\min c^T x$, subject to $Ax=b, x \geq 0$. Suppose that this program and its dual are feasible. Let $\lambda$ be the optimal solution of the dual. If the $k$th constraint ...
6
votes
1answer
243 views

Subset of matrix rows with half of column sums

Consider the following problem. We are given a matrix $A = (a_{ij})_{i,j = 1}^{m,n}$ with $m$ rows and $n$ columns, all $a_{ij}$ are nonnegative. Prove that there exists a subset $S$ of rows, $|S| \...
6
votes
1answer
469 views

Is there a connection between duality in linear programming and duality in functional analysis?

In linear programming we optimize a linear function which is constrained by linear inequalities or linear equalities. Under some conditions you can rewrite the problem to the dual problem, so that you ...
6
votes
1answer
844 views

Easy elementary proof of Farkas Lemma?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem? What about special case below: If the Matrix $A$ is invertible, then there is ...
6
votes
1answer
174 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
6
votes
1answer
943 views

What is graph theory interpretation of this linear programming problem?

So, I am looking at a paper by Rosenfeld, "On a problem of C.E. Shannon in graph theory", where he gives necessary and sufficient conditions for a graph $H$ to satisfy $$\alpha(G \boxtimes H) = \alpha(...
6
votes
1answer
3k views

Formula for position in an upper triangular matrix

I'm currently working on the Travelling Salesman's Problem in a computer science module. I have implemented some linear programming techniques using the software lp_solve. I've ended up with an upper ...
6
votes
1answer
6k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
6
votes
1answer
329 views

Under what conditions minimax is equivalent to maximin?

Under what conditions $$ \min_{x} \max_{y} f(x,y) = \max_y \min_x f(x,y) $$ ?
6
votes
2answers
837 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?
6
votes
1answer
589 views

Integer linear programming constraint for maximum number of consecutive ones in a binary sequence

Consider an integer programming problem with binary decision variables $x_1,\ldots,x_n \in \{0,1\}$. Im trying to model the constraint that enforces the maximum number of consecutive ones in ...
6
votes
0answers
623 views

Solving $Ax = b$ for non-negative $x$ given boolean matrix $A$ and non-negative $b$

I am trying to solve $Ax = b$ with the following properties: $A$ is a boolean (aka. logical, binary) matrix, i.e., each entry in $A$ is either $0$ or $1$ $A$ is of size $m \times n$ where $m \ll n$ ...
6
votes
1answer
1k views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
6
votes
0answers
860 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} f(x)p(x)...
6
votes
0answers
115 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
5
votes
2answers
10k views

Minimizing the sum of absolute values with a linear solver

I need a linear program to minimize the sum of several absolute values, but the inclusion of an absolute value means the linear solver won't work. I know there are ways around using an absolute value, ...
5
votes
1answer
4k views

Duality. Is this the correct Dual to this Primal L.P.?

Given a problem: Find the dual: $$ Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ ...
5
votes
2answers
8k views

How Can $ {L}_{1} $ Norm Minimization with Linear Equality Constraints (Basis Pursuit / Sparse Representation) Be Formulated as Linear Programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
5
votes
3answers
11k views

How to find out whether linear programming problem is infeasible using simplex algorithm

So in http://econweb.ucsd.edu/~jsobel/172aw02/notes3.pdf, there is a mention about finding out whether linear programming (LP) problem is infeasible by simplex algorithm, but it does not actually go ...
5
votes
2answers
2k views

In a linear program, how to add a conditional bound to x?

I am working with a standard linear program: $$\text{min}\:\:f'x$$ $$s.t.\:\:Ax = b$$ $$x ≥ 0$$ Goal: I want to enforce all nonzero solutions $x_i\in$ x to be greater than or equal to a certain ...
5
votes
5answers
2k views

Find a convex combination of scalars given a point within them.

I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me. Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...
5
votes
1answer
3k views

Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.
5
votes
2answers
561 views

minimize $c^tx$ subject to $Ax=b,x\ge0$ dual problem

Consider the linear program to minimize $c^tx$ subject to $Ax=b,x\ge0.$ Write the dual problem. Drew Brady user helped me to do this but I still have doubts about it. First off, the lagrangian ...
5
votes
3answers
914 views

How to check whether a convex polyhedron is contained in another convex polyhedron?

Suppose we have two convex polyhedra $$P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$$ $$P_2=\{x\in \mathbb{R}^n \mid A_2 x \geq b_2 \}$$ Is there a way to check whether $P_1 \subseteq P_2$? I ...
5
votes
4answers
7k views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
5
votes
2answers
295 views

Integer programming formulation of the partition problem

I have the following problem: Consider the set of integers $\{1,2,3,4,5,6\}$ and $$\sum_{i=1}^6 s_i i,$$ where $s_1, s_2, \dots, s_6 \in \{1,-1\}$ are the signs that appear in front of each of ...
5
votes
1answer
78 views

How to graph system of equations.

I have solved every question except show the information on a graph and find the number of each type of tent that must be hired; I have put my problem in quotations, down below in the midst of the ...
5
votes
1answer
5k views

simplex method : Entering Variable

In the Simplex method, a variable that enters the basis, cannot depart the basis in the very next iteration. Please explain..why so ?
5
votes
3answers
112 views

How to verify whether or not there exists a vector $x$ such that $Ax > 0$?

Given a matrix $A$ in $\mathbb R^{m\times n}$, if I want to know whether or not there is an $x \in \mathbb R^{n}$ such that $$ Ax > 0, $$ (meaning all elements in $Ax$ are positive). Is there some ...
5
votes
2answers
187 views

Almost a linear program. How to solve efficiently?

How can one go about solving this optimization problem efficiently? Unfortunately it is a maximization instead of a minimization, which stymied my attempts at converting it into an LP. $$ \mbox{...
5
votes
1answer
192 views

A particular ILP where the existence of a relaxed solution implies the existence of an integer solution

This question emerged from a discussion on my previous question Determining quickly whether this Integer Linear Program has any solution at all, which I would like to elaborate separately. I am ...
5
votes
1answer
6k 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.
5
votes
1answer
159 views

linear programming for bus tickets

Hi I work as a programmer at a bus company and I need to implement a ride initialization request. I think it might be a linear programming problem but I'm not sure and I ask for some help :) A ...
5
votes
2answers
7k views

Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
5
votes
1answer
1k views

Determining quickly whether this Integer Linear Program has any solution at all

I've got an integer linear program of the form $$ \begin{aligned} \text{Minimize}&& c &= x_1 + \cdots + x_m \\ \text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\ \text{where} &...
5
votes
2answers
120 views

A property of a linear image of the cube

Let $[0,1]^3$ denote the unit cube in $\mathbb{R}^3$. Let $L : \mathbb{R}^3 \to \mathbb{R}^2$ be a surjective linear map, and let $H := L([0,1]^3)$ (which is generically a hexagon). Can you provide a ...
5
votes
1answer
290 views

How close are solutions of systems of homogeneous linear inequalities with close coefficients?

Suppose I have two systems of $n$ homogeneous inequalities of $k$ variables: $$Ax \geq 0$$ and $$Bz \geq 0,$$ where both $A$ and $B$ are $n \times k$ matrices such that for any $i=1, \ldots, n$, and ...
5
votes
3answers
534 views

Determining whether or not a vector is in a cone

Determine whether or not the vector $\langle 0,7,3 \rangle$ belongs to the cone generated by $$\langle 1,1,1\rangle \qquad \langle -1,2,1\rangle \qquad \langle 0,-1,1\rangle \qquad \langle 0,1,0\...
5
votes
2answers
140 views

Balancing recipe's ingredients through a system of linear equations: is it the right approach?

I have 4 ingredients that I want to combine to prepare a drink: ...
5
votes
1answer
5k views

How can I determine B-inverse from an optimal tableau of a LP?

(This is NOT a homework question, I am reviewing for my upcoming exam) Given this linear program: and this optimal tableau: I am attempting to determine $B$ inverse using the table above. From the ...
5
votes
1answer
4k views

optimal basis and optimal solution

Determine which of the following is true: a) Consider a maximization LP in SEF. Suppose $x$ is a basic feasible solution for which all nonbasic variables have strictly negative reduced costs. Then ...
5
votes
2answers
8k views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ x_1&&&-&...
5
votes
2answers
1k views

Why do we need duality in linear programming or convex optimization?

I'm learning convex optimization, just get started with linear programming, and there is such a thing as duality in linear programming. Here is my problems, why there is a dual problem for a linear ...