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

learn more… | top users | synonyms

0
votes
2answers
220 views

Calculation of volume and centre of mass of an arbitrary polyhedron

Hi I am developing a thesis that will calculate the volume and center of mass of an arbitrary block of rock. 1- The calculation starts with triple volume integrals. The formulas are transformed to ...
1
vote
1answer
180 views

Formulating a linear programming problem

I have the following problem: Now I would like someone to verify whether my answer is correct or not :) Here goes: If I denote the different alloys by $x_1, x_2, x_3, x_4, x_5$ I get ...
1
vote
1answer
2k views

Converting linear programming problems into standard form

I have the following linear programming problem: Convert the following problems to standard form: $$\begin{align} \text{a)}&\text{minimize}&x+2y+3z\\ & \text{subject ...
3
votes
0answers
59 views

On the bounds of the objective function in a standard LP

Consider a standard linear programming (LP) such as: \begin{align} \sum_{i=1}^{N}\frac{a_{i}}{b_{i}}x_{i}\end{align} \begin{align}\text{s.t. }\left ( \sum_{i=1}^{N}x_{i}=1 \; , \; ...
0
votes
2answers
60 views

How is it possible to use normals in the definition of a linear programming constraint?

I'm trying to calculate the center of a feasible region in a system of linear inequalities using linear programming techniques. After a bit of research, it looked like defining the center as a ...
2
votes
5answers
322 views

Compressive sensing with non square matrices

I'm implementing the algorithm in the following paper: "Compressive sensing for wideband cognitive radios" http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361 However I've run into a ...
0
votes
2answers
634 views

Help with proof: Hyperplane is an $(n-1)$-dimensional linear variety

I'm reading linear programming and I bumped into the following: I'm having trouble getting grasp on the proof of proposition 2. Could someone perhaps explain it to me in other terms? For some ...
0
votes
1answer
90 views

A linear programming problem

Please guide me on the following question. Consider the LP problem maximize $x_1+x_2$ subject to $x_1-2x_2\le10$ $x_2-2x_1\le10$ $x_1,x_2\ge0$ Which of the following ...
1
vote
2answers
79 views

How to determine this?

For any 6 coplanar points $\left(x_{1}+y_{1},x_{2}+y_{2},x_{3}+y_{3}\right)$, $\left(x_{1}+y_{2},x_{2}+y_{1},x_{3}+y_{3}\right)$,$\left(x_{1}+y_{3},x_{2}+y_{2},x_{3}+y_{1}\right)$, ...
0
votes
2answers
62 views

getting sign of LP solution variables

I have an LP where I'm only interested in the sign of some of the variables of an optimal solution. The value itself does not matter. Currently I'm using cplex to get an optimal solution and take the ...
1
vote
2answers
354 views

Linear programming simplex - can I have a constraint with a multiplication?

I'm not sure of this, can I have a constraint like this in a linear programming problem to be solved with simplex algorithm? $$n_1t_1 + n_2t_2 > 200$$ where $n_1$ and $t_1$, $n_2$ and $t_2$ are ...
0
votes
1answer
533 views

Programación Lineal (PL)

quería ver si me pueden ayudar en plantear el modelo de Programación Lineal para este problema. Sunco Oil tiene tres procesos distintos que se pueden aplicar para elaborar varios tipos de gasolina. ...
0
votes
0answers
132 views

Linear programming with countably “infinite variables” and “finite constraints”!

Is it possible to do a linear programming with countably "infinite variables" and "finite constraints"? If not, what do you purpose? (Example Link): Maximum and minimum of an integral under integral ...
1
vote
0answers
15 views

How to find the best fit when you have a set of ideal ratios, but some of those are below a minimum?

Say you have a set of ideal ratios, whose sum = 1. For example, input = [0.2, 0.2, 0.3, 0.3] But suppose that there is a rule stating that every ratio should be ...
1
vote
1answer
87 views

Integral Polyhedra: Integer on each face

The general topic is unimodular matrices and integral polyhedra. I am really new to this field and I am studying for an exam in an advanced operations research course. In this case we are always ...
0
votes
1answer
43 views

Linear programming: what does the “test ratio” measure?

When reducing rows in linear programming you pick the one with the lowest test ratio in a certain column, why is that? What does the test ratio mean?
0
votes
2answers
83 views

Solve combinatorics problem to target desired result

I wonder if someone would be able to suggest some solution, programming technique or, at least, the right name for the problem, so I could research more. I have a problem where I given a number of ...
5
votes
0answers
571 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} ...
1
vote
0answers
63 views

Duality in Chebychev approximation

I got messed up with this problem and can't find any clue to solve this. Hope some one here can help me. Let $A$ be an $m \times n$ matrix an let $b$ be a vector in $R^{m}$. We consider the ...
3
votes
1answer
72 views

Is it possible to get logical and with linear operations?

I'm currently trying to model a problem with GLPK. I am in a situation where I have two binary variables $a, b$ and I need a function $$f: \{0,1\}^2 \rightarrow \{0,1\}$$ such that $$f(0,0) := ...
0
votes
1answer
943 views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
2
votes
1answer
325 views

Duality and the Minimax Theorem

I review LP duality by reading Lecture 7: The LP Duality Theorem. I get the idea how to find the dual LP from primal LP, but my basic knowledge is not enough for finding dual LP for the LP in chapter ...
2
votes
1answer
103 views

Optimizing Rectilinear Distance Traveled

I have a simple pipe network like this (not to scale): I can place a "valve" on any point on that pipe. What the valve does is it permits a certain viscous fluid to fill the pipes. However, because ...
0
votes
1answer
81 views

possible to index a set by a variable?

I am trying to do something that logically should be possible to do. However, I am not sure how to do this within the realm of linear programming. I am using ZMPL/SCIP, but this should be readable ...
0
votes
0answers
37 views

Polytime programming

Given a linear system of the form: $$x_r = a$$ $$x_j = b$$ $$c_1x_1 + c_2x_2 ... c_nx_n = n$$ $$x_1 + x_2 + x_3 ... x_n = k $$ $$0 \leq a,b,x_1, x_2, x_3 ... x_n \leq 1$$ $$k \geq 0$$ How quickly ...
1
vote
0answers
136 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
1
vote
2answers
309 views

norms and sparsity

Could anyone please elaborate on why $L^2$ norm moves toward the outliers compared to $L^1$ norm. I mean, what property/quantity in the mathematical expression of the norms makes it perform such way. ...
1
vote
1answer
38 views

Does a linear expression exist for these ILP variables?

I am formulating an integer linear program. Suppose I have a set of binary variables $X_{i,j,k}$ that is $1$ if subject $i \in I$ is taught by lecturer $j \in J$ during timeslot $k \in K$, or $0$ ...
2
votes
1answer
39 views

how to choose positive symmetric matrix?

What are the ways to find a positive symmetric matrix $P$ such that $ A^{T}P+PA=-Q$ where $Q$ is also positive symmetric matrix, $A=\left[\begin{array}{cc} 0 & I_{n}\\ -K_{v} & -K_{p} ...
1
vote
0answers
139 views

simplified Linear programming model with time constraints

Based on my other question, here is a simpler hypothetical exercise that isolates that time constraint issue all together: A farmer has 1000 ha forest that is already at a mature age assumed to be ...
3
votes
2answers
207 views

Why do we need duality in linear programming or convex optimization?

I'm learning convex optimization, just get started with linear programming, and there is such a thing as duality in linear programming. Here is my problems, why there is a dual problem for a linear ...
1
vote
0answers
40 views

$X$ is a point in a bounded polyhedron $\ \in R^n $ with $n-1$ active constraints

Lets take a vector $d$ which is orthogonal to the active constraint. Since the polyhedron is bounded: We'll move to a point $x+\alpha*d$ where we will activate another constraint let's name it j. ...
0
votes
1answer
1k views

Will the feasible region always be convex in linear programming? [duplicate]

In linear programming we find a feasible region , is this region always convex? . if a concave region is found where objective is minimization , I think then a solution exists . Advance thanks. ...
0
votes
0answers
26 views

Vertex Set Optimization

I have the following problem: Min $c^Tx$ Subject to: $Ax = b$ $x >= 0 $ Where A is an M x N matrix: But rather a single solution I would like to know the first K best solutions where $1<= ...
0
votes
1answer
82 views

Finding the dual of this primal LP.

I am going over sample questions from a sample exam, and I got stuck on the following question. I need to determine the dual of this LP: $min: c^Tx + d^Tu \\ s.t: Ax + Du = b\\ x \ge 0$ $A$ is an ...
1
vote
0answers
435 views

How does Microsoft Excel Solver's Simplex algorithm deal with integers?

I was wondering how the Simplex algorithm in Excel's Solver deals with integers. From what I understand, the Simplex algorithm is meant to be used for linear programming/optimizations only. Yet, Excel ...
1
vote
0answers
61 views

Vertex Definition (Linear optimization)

I don't understand a definition of the vertex over a convex polyhedron in standard form : $P=\{x\in\mathbb{R}^n, Ax=b, x \geq 0\}$ $x$ is a vertex of P if and only if the columns $\{A^j\in ...
1
vote
1answer
408 views

Absolute value optimization

If you have an LP Maximize/Minimize: $c_1|x_1| + c_2|x_2| ... c_n|x_n|$ Subject to: $Ax = b$ Can this be solved in polynomial time with respect to the amount of data used to represent the ...
5
votes
1answer
132 views

Under what conditions minimax is equivalent to maximin?

Under what conditions $$ \min_{x} \max_{y} f(x,y) = \max_y \min_x f(x,y) $$ ?
0
votes
1answer
83 views

Describing a set using linear inequalities

I am having a hard time understanding the answer to the following exercise (which was taken from "Linear Optimization and Extensions: Problems and Solutions" by Padberg and Alevras). My problem ...
0
votes
1answer
59 views

Clarification needed for this linear programming problem

I am stuck on the following problem: I have got only confusion over option (1). The options (2) ,(3) are correct and option (4) is wrong. But how can I check whether the problem has more ...
3
votes
4answers
6k views

Converting absolute value program into linear program

I have the generic optimization problem: $$ \max c^T|x|$$ $$ \text{s.t. } Ax \le b $$ $x$ is unrestricted How do I convert it into a linear programming problem? Online I read something about ...
1
vote
0answers
109 views

Linear Programming change of right hand side

The question is the following: Given a linear program: $\min_{x \in \mathbb{R}^n} c^Tx, Ax=b, x\ge 0$, where $x\ge 0$ means, that all components of $x$ have to be greater equal $0$. Further we know ...
2
votes
2answers
3k views

Solving a linear program in case of an equality constraint

I had asked a question, which can be found here : http://stackoverflow.com/questions/17232596/computing-the-optimal-combination And had been suggested Linear programming. I have looked up Linear ...
1
vote
0answers
32 views

If the following LP has an integral solution

I know the constraints matrix A of a linear program "Min cx such that Ax>=b" is totally unimodular. So, the program has integral solutions for integral vector b. If this is also the case for the ...
3
votes
1answer
67 views

Rewrite constrained optimization objective

I wanted to ask, under which conditions can one rewrite the optimization objective $\min_x f(x)\;\;\;s.t.\;\;\;g(x) \leq s$ as $\min_x g(x)\;\;\;s.t.\;\;\;f(x) \leq t$ I have particular interest ...
3
votes
0answers
117 views

weak duality theorem

Studying duality theory I have not found clear this point considering the primal a minimize problem, if x and p are feasible solution to the primal and to the dual then $p^tb \leq c^tx$ for ...
2
votes
0answers
81 views

Existence of a Linear Optimization Problem

I am working on a linear static optimization problem. I found a solution to the problem. However, I want to formally check the solution existence. I tried some methods but I don't know if it is enough ...
1
vote
2answers
214 views

Changing the Parameter in Linear Programing, Changes the Solution to the Dual

Consider a linear optimization problem such that the RHS of the constraints depends on a parameter $a$, as in $$Ax=b+ae_j$$ Here $e_j$ is a unit vector in the direction of $x_j$. Suppose that for ...
1
vote
1answer
629 views

linear programming constraint for conditional

I having formulating the following (what should be fairly simple) ilp constraint. Basically let $p$ be a binary variable and $s$ be an integer that is greater than or equal to 0. The constraint is ...