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

learn more… | top users | synonyms

3
votes
1answer
113 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 ...
4
votes
1answer
486 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} ...
8
votes
2answers
5k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value ...
4
votes
1answer
847 views

How to solve system of equations with multiple constraints?

I have a system of equations that looks like this: $$\begin{array}{rl} a_1 b_1 c_1+a_2 b_2 c_2+a_3 b_3 c_3&=1000\\ a_1+a_2+a_3&=1\\ a_2&=0.6 \,a_1\\ b_1+b_2+b_3&=500 \end{array}$$ ...
1
vote
1answer
304 views

positive solution of a system of linear equations

Consider the following system of linear equations over $x_{ij}$ for $1\leq i\leq m$ and $1\leq j\leq n$: $\sum_{j}x_{ij}=a_i$ for $i=1, \cdots, m$ and $\sum_{i}x_{ij}=b_j$ for $j=1, \cdots, n$ where ...
2
votes
2answers
405 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
3
votes
2answers
139 views

Terminology: Linear 'programming'

What is the origin of the term 'programming' in 'linear programming'? It is not obvious to me why this should be called a type of programming.
1
vote
1answer
291 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
1
vote
1answer
2k views

What is the meaning of the linear programing problem solution's outputs?

I have difficulty to understand its output. Here is the problem: max 2x + 3y s.t. 4x + 3y <= 10 3x + 5y < 12 end I get this output: ...
2
votes
1answer
89 views

Minimim steps required based on game logic

I have the following simple game logic. You start with G gold and 0 experience at Time = 0 minutes. There are different types of houses what you can build, each with his own properties. House A ...
2
votes
1answer
108 views

Stretching of a set of numbers to align to a reference

I am trying to align an ordered set of n real, strictly positive numbers $$Q = {q_{1},q_{2},..., q_{n}}$$ to a reference set of the same size and with the same properties $$R = {r_{1},r_{2},..., ...
2
votes
2answers
1k 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 ...
3
votes
1answer
143 views

Solving ill posed linear equations

Given a set of linear equations $AX=B$, say $A$ is an ill posed matrix (has a few singular values equal or very close to zero), which numerical algorithm (conjugate gradient, least squares or steepest ...
1
vote
2answers
606 views

Invertability of submatrix?

If I have a matrix $A \in R^{(m \times n)}$ with $m \leq n$. All rows in matrix a are linearly independent and therefore $A$ has a full row rank. I can decompose matrix $A$ such that $A = [B|N]$ with ...
2
votes
2answers
325 views

Simplified nurse scheduling problem

I'm currently handling a project with a problem that is very similar to nurse scheduling problem in many respects. It is a part time workforce scheduling system whereby we need to determine which ...
1
vote
1answer
85 views

Vizualisation about line search in Linear Programming?

I am trying to visualize this recursive algorithm in LP, Wikipedia here. I am looking for references about in which kind of problems is this used and what does it really look like? I am also ...
3
votes
1answer
297 views

Steps in the Simplex Method

I'm trying to look at how the Simplex method in standard form works. I understand the basics of how ti works, but I can't understand what happens between two steps. I'm using the example from chapter ...
1
vote
1answer
339 views

“Base is degenerate IFF its corresponding basis matrix is singular”: degenerate with solution and degenerate without solution?

Statement "Base is degenerate IFF its corresponding basis matrix is singular" is wrong according to my Linear-programming teacher Mat-2.3140 in Aalto University (translated from Finnish here/here) ...
1
vote
0answers
403 views

Linear programming: writing a problem with artificial variables?

Use artificial variables to write a linear programming problem in canonical form with non-negative resource vector whose solution will determine whether there exists (and if so, find) non-negative ...
3
votes
0answers
58 views

finding the largest $p$ components of $x$

Given an $n \times n$ matrix $A$, and an $n \times 1$ vector $b$, the conventional way of computing an $n \times 1$ vector $x$ such that $x=Ax+b$ is to use the following iterations: ...
6
votes
1answer
373 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) = ...
1
vote
1answer
90 views

Is this linear programming problem right?

The problem is: Beth works a maximum of 20 hours/week programming computers and tutoring math. She receives 25 dollars/hour for programming and 20 dollars/hour for tutoring. She works between 3 and 8 ...
2
votes
1answer
437 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
2
votes
1answer
536 views

Linearizing min function Problem

How can I linearize $\min(x_1,x_2,x_3)$ in a maximization linear programming problem? Please help me. I've tried many things but I didn't solve.. My LP equations are as follows: Objective function ...
1
vote
2answers
104 views

Linear programming: expressing the fact that precisely $k$ variables are nonzero

Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero? I suspect this would already be enough to simulate ...
1
vote
1answer
123 views

Is this use of the simplex method correct?

I am trying to implement a simplex algorithm for solving LP task. I will post the question and my solution as well - what I need to know is whether my solution is correct, thanks in advance! ...
9
votes
5answers
5k views

Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...
0
votes
1answer
309 views

Interpolation of sin/cos

I am trying to optimize sin/cos for my MCU in order to calculate geo distance. This part of formula particularly is using trigonometry: ...
2
votes
1answer
177 views

Convert problem to linear programming task

I have function $\max \{ |x-1| + 2|y-1| | x,y \in R, x+y \leq 2 \}$. Can this problem be converted to LP? I think it cant because of the abs. value in criterial function, but Im not sure. If it can, ...
1
vote
1answer
85 views

Are these linear programming constraints correct?

The problem is: Beth works a maximum of $20$ hours/week programming computers and tutoring math. She receives $\$25$/hour for programming and $\$20$/hour for tutoring. She works between $3$ and $8$ ...
1
vote
1answer
370 views

Directly from primal to dual when primal not in standard form

This is a simple problem, but after spending some hours with linear programs in the primal and its dual form, I still can't do it quite intuitively for LPs which are not in the standard form. I know, ...
1
vote
1answer
83 views

Correlated Equilibrium - Transforming a non-linear objective function into a linear one

I am trying to transform a non-linear objective function into a linear one, in order to create a LP. How might I go about to do this (I have never taken a course in linear programming). I have that I ...
4
votes
5answers
716 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 ...
1
vote
0answers
50 views

Duality gap in cone programming

Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $$ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K ...
1
vote
0answers
25 views

Sufficiency of the condition for this linear programming problem to have solutions.

I'm looking for $x_1,x_2,x_3$ which satisfy the following constraints: $$ \begin{align*} &x_1,x_2,x_3\geq 0\\ &x_1+x_2\geq a\\ &x_2+x_3\geq b\\ &x_3+x_1\geq c\\ &x_1+x_2+x_3=1 ...
2
votes
3answers
144 views

Dual of a Linear Program

\begin{align} \min_{x} c^Tx \\ s.t.~Ax=b \end{align} Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by \begin{align} \max_{\lambda} \lambda^Tb \\ ...
1
vote
1answer
185 views

How does the two phase method for linear programs work…

I understand that by adding artificial variables the problem can be reformulated as a new problem where the "starting point" is readily found. What I don't get is how when this extended problem is ...
3
votes
1answer
448 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 ...
2
votes
1answer
51 views

Why can't the hyperplane H intersected with polyhedral set S contain any line…

S is the polyhedral set $ S = \{ \mathbf{x} \in \mathbb{R}^{n} ; \mathbf{Ax}=\mathbf{b}, \mathbf{x} \ge \mathbf{0} \} $ and $ H : \mathbf{c}^{T}\mathbf{x} = \beta $ with $ \min_S ( ...
1
vote
1answer
156 views

Linear programming - task formulation

I have a question concerning the formulation of a linear programmign task. I am trying fo find $x^* \in argmax_{x \in R^n}\{ a_1x_1 + a_2x_2, a_2x_2 + a_3x_3 + a_4x_a, a_4x_4 + a_5x_5 \}$, subject to ...
7
votes
2answers
2k views

What are the advantages of dual of a problem

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
3
votes
4answers
865 views

Finding the minimal cost edge cover for a bipartite graph

I have got two sets of elements and a pruned graph of bipartite edges with weights assigned to each edge. I need to find the minimal set of edged with the minimum cost covering all nodes from both ...
2
votes
0answers
191 views

Determine if a polyhedron is a polytope

Note, a polyhedron is the intersection of finitely many half spaces in $\mathbb{R}^n$ and a polytope is a bounded polyhedron. Let $M$ be an $m \times n$ matrix of integers. Let $P$ be the (possibly ...
0
votes
2answers
346 views

Convex function from Hessian

Am I correct to say that the following function is convex? $$\begin{align} & f(x,y)=-\sqrt{xy} \\ & x>0,y>0 \\ \end{align}$$ After computing the Hessian: $$ Hf =\left[ \begin ...
1
vote
2answers
691 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
4
votes
1answer
533 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\\ ...
2
votes
1answer
132 views

Critical Points. Find and classify.

Given $g(x,y)=y^2 - x^3$ find the critical points and classify them $$\nabla g(x,y) = \begin{pmatrix} -3x^2 \\ 2y \\ \end{pmatrix}$$ So, $\implies -3x^2=0,2y=0$ ...
0
votes
1answer
1k views

Linear Programming question- optimal solution

A film producer is seeking actors and investors for his new movie. There are n available actors; actor i charges $s_i$ dollars. For funding, there are m available investors. Investor j will provide ...
1
vote
1answer
79 views

Question on Linear Algebra

NOTE: I tried hard and came up with a lose proof, I have posted it as a answer. Do comment/correct if you can. Let $$P=\{x|Ax\geq b\}, A\in \mathbb{R}^{m\times n}$$ $$Q=\{y|Gy\geq h\},G\in ...
3
votes
3answers
241 views

0-1 knapsack like - the set of all non-contained affordable binary selections

This is my first question here, so please go easy on me :) The following problem is – I think - similar to the 0-1 knapsack problem. It's simplified somehow in that each item has only a cost ...