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

learn more… | top users | synonyms

0
votes
1answer
1k views

Example about the Reduced cost in the Big-M method?

I want to gather examples about the reduced cost in different cases, now for the Big-M method. I hope this makes the methods more accesible. So How does the Big-M method work with the below? ...
1
vote
1answer
306 views

Meaning of the bar over $\bf{c}'$ in $\bf{\bar{c}}'=\bf c' -\bf c'_B \bf B^{-1} \bf A\geq \bf 0$?

I am trying to understand the page 87 Bertimas about Linear Programming. The author uses bolding and bars -- now I am starting to think that the bar means something else to vector, bolding apparently ...
1
vote
1answer
480 views

Reduced cost in the Phase II of the two-phase Simplex?

My lecture slides outline how the two-phase simplex works: this table shows the end result of the phase I for the standard-form problem and the auxliary table of the phase I here. I understood until ...
0
votes
1answer
342 views

Reduced cost vector in the phase I of the Two-phase simplex?

I am trying to understand the part in red. The left is the standard form problem and the right is the auxiliary problem. Now I can understand until the red i.e. $\bar c =(-1,-1,-3,-1,-2,0,0,0)$. The ...
6
votes
1answer
79 views

Bounding the number of nonzero coefficients in a conic combination

I'm looking for a proof for the following statement in order to understand a proof about integer programming I'm reading. Given vectors $x_1, \ldots, x_s \in \mathbb R^n$, nonnegative coefficients ...
0
votes
1answer
26 views

Is it possible to slove problem with norm constraints using only linear programming?

The problem is $\min_x w^Tx$ s.t. $Ax=b$ $||x||_2=1$ Is there any tricks to handle the norm constraints such that the problem can be solved by only using linear programming tools?
0
votes
1answer
64 views

Optimum exists but not extreme point in Standard Form LP problem?

Standard form problem $$\min \bar c^T \bar x \text{ so that } A \bar x=\bar b, \bar x\geq \bar 0$$ I am thinking the point II (Finnish) i.e. optimum exists but it is not extreme point, why it ...
2
votes
1answer
454 views

Linear programming problem with no objective function

I have a binary integer programming problem for which I only need a solution that meets all the constraints. I do not have an objective function that I am trying to minimize or maximize. I've been ...
2
votes
1answer
2k views

Armijo's rule line search

I have read a paper (http://www.seas.upenn.edu/~taskar/pubs/aistats09.pdf) which describes a way to solve an optimization problem involving Armijo's rule, cf. p363 eq 13. The variable is $\beta$ ...
1
vote
1answer
31 views

-$\infty$ cost in unconstrained LP problem?

I am trying to understand this lecture slide (Finnish) and the point in bold. It is a part of an OR condition, this is how I understand it. I cannot understand the optimal cost statement. Example ...
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
235 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
159 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
935 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
217 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
718 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
362 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
352 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
611 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
239 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
108 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
202 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
965 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
446 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
242 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
252 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 ...