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

learn more… | top users | synonyms

0
votes
0answers
36 views

Simplex minimum ratio test fails on bounded problem

Consider the linear program $\max 3x_1 + x_2 \ @ \\ 3x_1+2x_2 -s_1 = 1 \\ 2x_1+x_2 +s_2 = 2 \\ x_1 \geq 0$ Leting $x_2 = x_2^+ + x_2^-$, introducing slack and solving phase 1 gives $\textbf{x}_b ...
0
votes
1answer
33 views

Linear regression with constrained weights

I have a set of $n$ linear combinations, each with $m$ parameters and desired value $b$. I want to find the set of weights $w$ which minimizes the total equations distances (e.g. the sum of distances ...
0
votes
1answer
15 views

Optimization relaxtion quesiton

I have the following LP relaxation of an integer programme (the programme formed from the set cover problem) minimize $\sum_{j=1}^{m} w_{j}x_{j}$ subject to $\sum_{j:e_{i} \in S_{j}} x_{j} \geq 1$ ...
2
votes
0answers
68 views
+100

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
0
votes
1answer
28 views

Dual part of complementary slackness

The proof of the complementary slackness of P: min $c^Tx $ @ $Ax = b, x \geq 0$ D: max $b^Ty $ @ $A^Ty \leq c$ Goes something like $c^Tx = b^T y = y^TAx \Leftrightarrow c^Tx-y^TAx = 0 ...
1
vote
1answer
42 views

Linear Optimization: Objective function value, basic feasible solutions and reduced cost

For the system $$Ax=b, x \geq 0$$ for $A \in \mathbb{R}^{m \times n}$, $m \leq n$, we call a set $B \subseteq \{1, \dotsc, n\}$, $|B|=m$ a basis for $A$, if $A_B$ is invertible, where $A_B \in ...
0
votes
0answers
11 views

Bicritiera combinatorial/linear optimization problem with an exponential number of non-dominated extreme point

In [Ruhe 1988] an instance of a bicriterial combinatorial optimization problem is constructed such that the number of non-dominated extreme points is exponential in the input size. Are there any ...
0
votes
1answer
36 views

Model logical constraints without binary variables?

Is it possible to express "either $f(x) \leq 0$ or $g(x) \leq 0$" where $f,g$ are linear constraints by using a finite number of continuous constraints/new variables, WITHOUT breaking convexity or ...
0
votes
1answer
31 views

Combining multiple linear programming to minimize the sum

I have a math problem that looks like a bunch of linear programming problem combined where A matrix is shared. Here is the math definition of my problem Minimize \begin{align} & p_1 (x_{11} + ...
1
vote
2answers
34 views

Is Linear Programming a Combinatorial optimization method?

I want to know LP can be considered as a Discrete optimization or continuous. The solutions can be fractions so it should be continuous. Please suggest. thanks
0
votes
0answers
27 views

linear programming slater condition

I am wondering if anyone could help to come up with a such example: ...
1
vote
1answer
52 views

Representation of a point in terms of extreme points and extreme directions in a LP feasible region

We know that every point in a feasible region (X) of a Linear Program can be represented as a convex combination of the extreme points of X plus a non-negative combination of the extreme directions of ...
1
vote
1answer
44 views

Can number of constraints be less than number of variables in Linear Programming?

In standard form of LP we have $n$ variable and $m$ constraint. In simplex algorithm we set all non-basic variable to zero and at most $m$ basic variable have positive value. if $m < n$, then at ...
2
votes
0answers
115 views

Nested optimization problems solving using mixed integer linear programming

Let us have two vectors of decision variables, $\mathbf{x}$ and $\mathbf{y}$, two linear objective functions, $F \left( \mathbf{x}, \mathbf{y} \right)$ and $f \left( \mathbf{x} \right)$, and two sets ...
1
vote
1answer
24 views

Job scheduling to minimise squared completion times using mixed 0-1 quadratic program

I have come across an Optimization question as follows: There are $n$ jobs that have to be processed on a machine. The machine can process only one job at a time. The time taken to process job ...
1
vote
1answer
67 views

Problem understanding proof involving determinant

I have problems understanding Theorem 3.2, page 29 from Theory of Linear and Integer Programming. I don't understand (3): Let $M$ be a matrix in $\mathbb{Q}^{n\times n}$, and let $M_{ij} = ...
2
votes
1answer
29 views

Dropping Upper Bounds in a Linear Program

Can anyone explain why usually, in a Linear Program, the upperbound constraints are "redundant" and then they can be dropped? For example, consider: ...
0
votes
1answer
20 views

Equality of polyhedra

Is a minimal representation for a polyhedron unique? And if so can we use this to prove that two polyhedra are equal (or maybe the same is a better definition).
1
vote
1answer
108 views

Linear programming algorithm that minimizes number of non-zero variables?

I have real world problems I'm trying to programmatically solve in the form of $$Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$$ Subject to \begin{align} & a_{11} x_1 + a_{21} x_2 + \cdots + a_{n1} ...
0
votes
0answers
25 views

What is the complexity of Simplex Method's Phase 1?

What are the average and worst-case complexities of the Phase 1 of the Simplex Algorithm? Is it respectively polynomial and exponential as well? Google search did not yield any results unfortunately. ...
0
votes
1answer
73 views

Solve Karush–Kuhn–Tucker conditions

solving a constrained optimizing problem with equality constraints can be done with the lagrangian multiplier. (http://en.wikipedia.org/wiki/Lagrange_multiplier) This approach leads to a system of ...
1
vote
1answer
39 views

linear programming problem - how much additional resources should I buy?

I have the following linear optimization problem: Maximize $$\sum_{i=1}^{n}x_{i}B_{i}$$ subject to the constraints $$a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n \le l_1$$ $$...$$ ...
2
votes
1answer
29 views

improving symbolic generation of objective function for optimization

I am currently using matlab to solve an optimization problem. I am generating the objective function using the symbolic toolbox. I planned use the symbolic toolbox to calculate the gradient and ...
1
vote
0answers
37 views

Computing the Optimal Simplex Tableau for Linear Programming

I am learning in my class about computing the optimal simplex tableau. I learned that, if you have an initial basic feasible solution, you can apply a series of formulas to compute the optimal ...
1
vote
1answer
45 views

Solving a linear optimization problem with products and work benches

I am taking a linear algebra course and I have a homework assignment of: A factory produces 5 products T1, T2, T3, T4, T5. Products are made on 3 different work benches P1, P2, P3, which can be used ...
5
votes
1answer
119 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...
1
vote
0answers
25 views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
0
votes
0answers
81 views

Dual problem of a linear programming example with an unrestricted variable

I have been asked to find the dual of the following (P): Min $Z= x_1+ 2x_2+ 3x_3$ Such that $$-4x_1 +3x_2 +5x_3=5$$ $$x_1+ 2x_3 \geq 4$$ $$x_1,x_3\geq0$$ $$x_2 \ \text{ unrestricted}$$ I ...
2
votes
1answer
44 views

Description of a constraint for a mixed integer program.

Suppose we have 100 items that are labelled from the set $P = \{A, B, C, D, E\}$. My constraints are as follows: I want to choose exactly seven items. The choice should have at least one item of ...
1
vote
1answer
32 views

Removing a max function in the constraints

Can the following problem be transformed into a linear programming problem: Find $x_1,..,x_N$ which maximizes the objective function $$\sum_{i=1}^{N}x_{i}\sum_{j=1}^{n_{i}}c_{ij}$$ subject to the ...
1
vote
0answers
33 views

Generating primal solution from dual solution of a LP

How to get the primal solution from a dual solution in general? For example, let the primal problem is $$ \text {maximize } 2r_1+2r_2-2c_1-2c_2 $$ where $$ r_1-c_1\leq1\\ r_1-c_2\leq1\\ ...
0
votes
1answer
12 views

Efficient algorithm for slightly generalized attribution problem

I have what I believe is an attribution problem: Given an $m \times n$ matrix, I need to select $p = \min\{m,n\}$ elements maximizing their sum such that they do not share a row or column. More ...
0
votes
0answers
28 views

If the supremum is finite, then the value is attained.

In a linear programming proof we have the: $\sup\{c^Tx: Ax \le b\}$ This supremem can be $\infty$, or defined as $-\infty$, if there are no vectors x such that $Ax \le b$. But it is stated that ...
0
votes
1answer
50 views

Optimization Problem - Lowest Total Price from Multiple Suppliers

I believe this is a linear algebra problem, but if not please let me know: Say you have 4 suppliers. You want to order 4 different items. The 4 suppliers each have a different price for each item and ...
0
votes
2answers
34 views

Minimization problem, both terms in function positive

I have the following problem: Using the simplex method, minimize $z = 10x + 3y$ given the following conditions: $$2x + y \le 12$$ $$4x + y \ge 12$$ $$2x + y \ge 8$$ I've been told that minimizing ...
0
votes
1answer
37 views

MINLP optimization with matlab reaching different solutions every run

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. I describe the problem in more ...
0
votes
1answer
50 views

matlab MINLP optimization with ga

I have written a program for optimizing a set of generators. I have hourly price and cost data and need to figure out when a generator should run or just stay off. There are additional constraints but ...
0
votes
1answer
77 views

integer linear programing in matlab with the symbolic toolbox

I am writing a program to optimize a set of generators. I have hourly data and but dont want to necessarily optimize the whole time series. For a similar problem in the past I used the symbolic ...
1
vote
0answers
32 views

Modeling a lower-bound constraint on a euclidean distance in quadratic programming

I have been trying to model a certain problem into a mainly linear program, but with some quadratic constraints since I don't think that is something that can be avoided. I hope to solve it either ...
0
votes
0answers
27 views

Solution existence on $ax + by = c$

I have to produce an program which resolve the following equation: $ax + by = c$ With the following condition: $a$, $b$ and $c$ are known positive integer. $x$ and $y$ are positive ...
0
votes
1answer
50 views

Which algorithms are commonly used to solve this kind of Binary Integer Programming problem?

I want to solve the problem of minimizing $$\mathbf{c}^T\mathbf{x}$$ subject to the condition that $$A\mathbf{x} = \mathbf{b}\text{,}$$ where $\mathbf{b},\mathbf{c}$ are given vectors in ...
1
vote
2answers
51 views

Escaping from a point in linear programming

Is there a trick for explaining the following constraint as a set of linear (in)equalities? $$ \sum_{i=1}^n|x_i-a_i|>0, $$ where $a_i$'s are real constants.
0
votes
0answers
44 views

Algorithm to efficiently compute$ A^k$

If a symmetric matrix $A$ has SVD $A=U\Sigma U^{\top}$, then $A^k=U\Sigma^kU^{\top}$. What would be the most efficient algorithm to compute $A^k$ such that the worst case time complexity is as low as ...
1
vote
0answers
23 views

linear programming problem given initial solution

While dealing with a linear programming problem we usually try to start with the basic feasible solution corresponding to the identity Matrix in the coefficient matrix. I have no idea how to solve the ...
11
votes
0answers
235 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
0
votes
0answers
15 views

Polar cones' property [duplicate]

I am trying to prove: $A \subseteq B \implies B^\circ \subseteq A^\circ$ where $A^\circ$ is polar cone of $A$ ($A$ convex cone) and $B^\circ$ is polar cone of $B$ ($B$ convex cone)
1
vote
0answers
58 views

Prove $\lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)$

Prove the minimum directed cycle mean cost satisfies: $\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$ using the Bellman-Ford algorithm. Let ...
1
vote
1answer
43 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost.

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
0
votes
0answers
28 views

Calculating ONeill prices in combinatorial auctions using the dual (Linear programming)

I am trying to calculate the O’Neill prices[1] for the individual atoms in a combinatorial auction. The method is: Solve the IP to find the optimal allocation for the auction. Remove the integer ...
1
vote
0answers
29 views

How to create a linear set of proportions summing to 1?

I'm not even really sure what this concept is called. But my objective is to create, for any n, a linear distribution of numbers less than 1 summing up to and plateauing at 1. It would have to work ...