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

learn more… | top users | synonyms

0
votes
0answers
15 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
28 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
39 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
26 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
25 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
24 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
40 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
31 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
17 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
24 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
35 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
21 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
25 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
42 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
50 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
36 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
15 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
211 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

When can i solve simplex tableau

I saw exercises where they give an objective function ( without restrictions ) and a simplex tableau to be completed , if you can solve How do I know when it may solve the tableau ? What are the ...
0
votes
0answers
14 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
36 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
19 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
26 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 ...
1
vote
0answers
13 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 ...
1
vote
0answers
59 views

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

Prove an artificial variable that leaves the basis will never return. Edit: This is for the simplex method (I think). I have no idea how to start this. Anyone know any books with these kinds of ...
2
votes
1answer
77 views

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

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
2
votes
2answers
34 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
36 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
22 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
41 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$ ...
0
votes
0answers
16 views

Mathematical model for MILP optimisation problem- power scheduling

I am having trouble trying to formulate a mathematical model for the problem below to solve later as an MILP problem using different optimization software. I want to formulate the model so as to ...
1
vote
0answers
80 views

Formulating linear programming treatment plan based on costs, periods, and condition

Note that this question is cross posted from OR-exchange Although we have a software that solves this for us, I'd like to understand the background behind the scenes as well as build a validation ...
1
vote
1answer
26 views

Duality - linear programming

I have to find a respective dual programme for the given LP $$ \max \ 2 x_1 + 2x_2$$ s.t. $ -x_1 - x_2 \ge -5 \\\phantom{-}x_1,\phantom{,,}x_2 \ge 0$ I got this: $$\min \ 5y_1$$ s.t. $y_1 \ge 2 ...
0
votes
0answers
16 views

Can we find some of those variables verifying this inequality

Let us consider $7$ variables verifying these inequalities: $c>2$ , $x<y$ , $z>w$ , $t^{c}>t$ , $t>x$ , $z<B$ , $w<B$ My question is: Can we find some of those variables ...
0
votes
0answers
29 views

Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis. The description is as ...
2
votes
3answers
41 views

Prove $A_1, A_2, \ldots,A_{\ell-1}, A_{\ell+1}\ldots \ldots, A_{m} $ in $\mathbb R^m$ are linearly independent viewed as vectors in $\mathbb R^{m-1}$?

Suppose I have linearly independent vectors $A_1, A_2, \ldots, A_m$ in $\mathbb R^m$ Consider the matrix $B = [A_1, A_2, \ldots A_m]$ consisting of these vectors and suppose $B^{-1}[A_1, A_2, ...
0
votes
1answer
16 views

Find the largest lower bound that covers p percent of the data

Suppose that you have a finite set $X\subseteq \mathbb R$, and you want to solve the following constrained optimization problem Find $\max a$ such that $\frac{|\{ x \in X: x>a \}|}{|X|}\ge ...
1
vote
1answer
38 views

An inequality about Hermitian matrices

Say one knows the following statement, That for any Hermitian matrix $H$ with eigenvalues $\lambda_1 \geq \lambda_2 ..\geq \lambda_n$ one has, that in any basis, for any positive integers $1 \leq i_1 ...
1
vote
2answers
43 views

Combinations of fruits and their “nutrients”

As a computer scientist and not a mathematician, I know not some of the formal language to describe my problem, so I'll present it in a word problem form. Maybe someone can help me hone my search and ...
0
votes
0answers
15 views

How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. It is possible that the max-flow and min-cut is equal to $\infty$. However, reading ...
0
votes
0answers
26 views

How can I use Mehrotra's predictor-corrector primal-dual interior point method to solve a problem that is not in the form of cTx?

I am not very familiar with optimization methods. I am studying the paper "Blind channel identification for speech dereverberation using l1-norm sparse learning" (here: http://linyq.com/NIPS2007.pdf). ...
2
votes
1answer
30 views

Modeling with Linear Programming

Here is the scenario; Let's say that a wholesaler have a storage with the capacity of $75,000$ $m^3$. The stock of corn at the beginning of the year is $15.000$ $m^3$ and the working capital is $ ...
0
votes
2answers
24 views

Maximising radius of a circle inside a 2D shape

I'm given a set of inequalities which define constraints of a geometric shape. For simplicity, let's assume its a 2D object, say a triangle. I want to find the maximum radius $r$ of a circle $c$, that ...
0
votes
1answer
20 views

LP model constraint formulation

We have a production plant that for each ton of $a$ requires $p_x$ tons of $x$ and $p_y$ tons of $y$ and we must decide how much material to ship to this plant. Is it just $a = y/p_y = x/p_x$? Do I ...
1
vote
1answer
24 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
2
votes
1answer
46 views

Games on betting from a set

Two players each chooses a number from the set $\{1,2,4\}$ and correspondingly bets an amount of \$$1$, \$$2$, or \$$4$. There is no collaboration between players. Rules: $1.$ If the two chosen ...
3
votes
1answer
48 views

Upper bound on maximum absolute value of all subdeterminants of a matrix

Let $A \in \mathbb{R}^{m \times n}$ and let $\Delta(A)$ be the maximal absolute value of the determinants of the square submatrices of $A$. A simple lower bound would be $$ \Delta(A) \geq ...
2
votes
0answers
27 views

mathematical model of an assignment/scheduling problem

I am solving a scheduling problem and I am able to abstract it into an assignment problem of assigning 45 machines to 42 jobs. the assignment problem was given as having 14 jobs, each with 3 tasks and ...