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

learn more… | top users | synonyms

0
votes
1answer
47 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
308 views

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
53 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
172 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 \mathbb{...
0
votes
1answer
87 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
57 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
64 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
58 views

linear programming slater condition

I am wondering if anyone could help to come up with a such example: ...
1
vote
1answer
295 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 ...
1
vote
1answer
262 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 ...
3
votes
0answers
371 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
35 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 $i$...
1
vote
1answer
87 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} = a_{ij}/b_{...
2
votes
1answer
30 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: http://en.wikipedia.org/wiki/Set_cover_problem#...
0
votes
1answer
31 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).
3
votes
1answer
389 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
1answer
361 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
59 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$$ $$...$$ $$a_{m1}x_1+a_{12}x_2+\...
2
votes
1answer
81 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
92 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 tableau....
1
vote
1answer
94 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 ...
4
votes
1answer
416 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, x\...
1
vote
1answer
100 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 ...
2
votes
1answer
62 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
279 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
66 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\\ r_2-c_1\leq1\...
0
votes
1answer
30 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
62 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
73 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
41 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 $z$...
0
votes
1answer
73 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
170 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
222 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
119 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
1answer
81 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 $\mathbb{F}_2^...
2
votes
2answers
56 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
62 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
42 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 ...
14
votes
0answers
363 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 ...
1
vote
0answers
17 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
61 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
83 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 ...
1
vote
0answers
16 views

Optimizing a set of rules to better predict the outcome of events

I'm trying to better predict the top three finishers of the next 1000 800m mens freestyle swimming race. I've got a set of rules to rate the swimmers: 1) Add 5 points if the swimmer won his last ...
2
votes
0answers
173 views

Prove an artificial variable that leaves the basis will never return.

This is in the context of the Big M Method in the simplex algorithm in linear programming. Prove an artificial variable that leaves the basis will never return. I have no idea how to start this. ...
3
votes
1answer
889 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \...
2
votes
2answers
494 views

Can calculus optimization problems be turned into linear programming problems?

I found a Linear Programming textbook somewhere, and I skimmed through the first few pages. While I am not nearly enough ready to go through it, the things it dealt with seemed very much like calculus ...
0
votes
1answer
37 views

Calculating the distribution between a range without an MILP solver?

I am currently using a MILP calculation and I was wondering if anyone can recommend a more mathematically simplistic method of calculating this distribution and arriving at a similar result? Qty - ...
0
votes
0answers
54 views

Finding the Dual of a primal LP

Suppose that we have the following primal LP: $\min z=c^Tu+d^Tv \\ \mbox{s.t.}\ \ \ \ \ \ \ \ \ u+Av=b, u\geq 0, v\geq 0$ I want to find the dual problem of this LP but I am slightly confused as ...
2
votes
0answers
55 views

Can we ever have E(argmin(f)) = argmin(E(f))?

Consider a parametric real-valued function $f_{\boldsymbol{\alpha}}:\ \mathbb D^N \rightarrow\mathbb R$ whose parameters $\boldsymbol\alpha$ vary according to some distribution $\psi$, and $\mathbb D$ ...