Tagged Questions

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

learn more… | top users | synonyms

0
votes
0answers
81 views

linear equations with inequality constraints

The problem is, given a set of linear equations $Ax=b$ such that the system is under-determined, and a set of linear inequalities $Cx\geq 0$, find a solution for the system. Does anyone know a general ...
0
votes
2answers
160 views

Is an unit-cube polyhedron? What about other platonic solids?

Definitions According to my linear programming course and screenshot here (Finnish), a polyhedron is such that it can be constrained by a finite amount of inequalities such that $$P=\{\bar x\in ...
2
votes
1answer
49 views

What is the solution according to the following parameters? (equation)

The equation would accept x,y and output z where As X approaches infinity and Y approaches infinity, Z approaches 0 As X approaches infinity and Y approaches 0, Z approaches 0 As X approaches 0 and ...
2
votes
1answer
51 views

Is this a linear programming problem

If $x \in R^n$, then $\min \|x\|_{\infty}$ sub to $Ax = b$, $x \geq 0$ where $\|x\|_{\infty}$ is the infinity norm which is $\max\{\|x_1\|,\|x_2\|,\ldots,\|x_n\|\}$. If not then how can ...
3
votes
2answers
161 views

Find the point in a sub-space defined by linear constraints closer to an external point

I have the following $P \in \mathbb R^d$ A set of $k$ linear constraints $c_i \in \mathbb R^d,d_i \in \mathbb R$ I need to find the point $P_0$ that satisfies all the $k$ constraints (i.e. ...
0
votes
1answer
219 views

Formulate model

Carter Enterprises is a soybean trading company. Once a month a representative attends a commodity sale where he either buys or sells soybeans in bulk. Carter uses a local warehouse for storing ...
0
votes
1answer
62 views

Just formulate linear program

A company produces fragrances $A$, $B,$ and $C$. There is virtually unlimited market demand for these. Fragrance $A$ sells for \$$10$ per gallon, $B$ for $\$56$ per gallon, and $C$ for $\$100$ per ...
2
votes
1answer
52 views

Smooth Reformulation of NonSmooth Constraints

If I have something like : \begin{align} \min_x \max_i f_i(x) \end{align} I can reformulate this nonsmooth formulation as: $$\min_x z$$ $$z\geq f_i(x)$$ and I have a smooth formulation of the problem. ...
3
votes
1answer
234 views

Pivoting and Simplex Algorithm

I would like to understand exactly how the pivoting works geometrically in Simplex algorithm. What is meant geometrically by moving a vector into BFS and moving out one. Also, what is the geometrical ...
2
votes
0answers
158 views

fundamental theorem of linear inequalities

Do you know a proof for the fundamental theorem of linear inequalities, which does not employ an implicit use of the simplex algorithm? Let $a_1, \dots, a_n, b \in \mathbb R^m$. Then either $b$ is a ...
2
votes
1answer
184 views

Optimality Criterion and the Simplex Method

The optimality criterion states: If the objective row of a tableau has zero entries in the columns labeled by basic variables and no negative entries in the columns labeled by nonbasic variables, ...
2
votes
1answer
349 views

Polytopes and matrices

How can one show that the vertices of a polytope are the matrices contains 2 ones on each row and col? and if $M \in P$ is not a $Z_2$ matrix then $M$ is a derived ...
0
votes
1answer
931 views

Matlab question: Converting a permutation matrix into a vector showing row exchanges

Let me preface that I am an absolute beginner with Matlab. I am trying to perform $PA=LU$ factorization on a matrix, however I am having difficulty with the permutation matrix. When I execute ...
2
votes
3answers
205 views

How to formulate Unique value constraint in Integer Programming?

Given the following integer programming formulation, how can I specify that the variables are unique and none of them has the same value as the other one. basically ...
4
votes
1answer
62 views

How can the formula be found for this problem?

We have a truck that we need to completely fill up with merchandise. We have an infinite supply of merchandise of dimension $1\times1\times1, 2\times2\times2, 4\times4\times4, 8\times8\times8, ...
0
votes
1answer
102 views

Ratios and projections

Let's say a company manages two types of projects A and B. A type projects are more complex than B type projects. A study found that the ideally, a project manager can handle at the same time 2 type A ...
1
vote
1answer
128 views

How to determine maximum angles between vectors?

I'm attempting to distribute vectors with the same origin with a maximum angle of separation. Then if given a set of vectors, I want to determine how far from maximum separation they are. For ...
0
votes
0answers
39 views

Uncertaint linear program

I have a linear programming problem such that its set of constraints can be divided into two parts. The first part are general linear constraints and the second part are uncertain constraints. It ...
3
votes
1answer
216 views

Find the vertices of the polytope

Let $x,n$ be 2 integers with $x<n$. I need to find the vertices of the polytope $P$ of $2 \times n$ nonnegative matrices $A$ such that: The first row in $A$ is summed to $x$. $$\sum_{j=1}^n ...
1
vote
1answer
717 views

Warehouse Location Problem as an integer progam instead of a mixed-integer program

Given a set of costumers $M = \{1, \dots , m \}$ and a set of of factories $N = \{1, \dots , n\}$ we have $c_{ij} \geq 0$ costs to deliver to costumer $i \in M$ from factory $j \in N$ $F_j \geq 0$ ...
1
vote
0answers
359 views

Defining Dual problems in Linear programming optimization

I have this Primal problem: $ Max \sum\limits_{i=1}^{50} X_iC_i \\ S.T.\\ \sum\limits_{i=1}^{50} X_iw_i\le W \\ \sum\limits_{i=1}^{50} X_iV_i\le V \\ X_i \le 1 \\ X_i \ge 0 \\ $ Now according the ...
1
vote
0answers
58 views

optimization of number of cylinders in a cube

I must admit that mathematics is not quit my strongest skill, so I want to ask you from where should I start with a kind of simple problem. Please keep in mind that I'm just a newbie asking things ...
1
vote
0answers
67 views

LP to test if two Line Segments intersect

I would like to use a linear program to test if two given linesegments $\overline{ab}$ and $\overline{cd}$ do not intersect. In a high level description I would have an LP of the form $$min ...
3
votes
1answer
95 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
349 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
1answer
3k 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
608 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
238 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
271 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
107 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
199 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
1k 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
88 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
97 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},..., ...
1
vote
2answers
963 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
121 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
436 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
240 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
69 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
250 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
288 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
278 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
51 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
343 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
71 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
317 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
391 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
1answer
87 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
103 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! ...
7
votes
5answers
3k 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 ...