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

learn more… | top users | synonyms

0
votes
0answers
29 views

What is (if there is) the generic term for equalities and inequalities

I'm writing a text about a particular linear programming (LP)I optimization problem, that is described using a mixture of inequalities (, ...
0
votes
1answer
18 views

About finding the common diagonalizing similarity transformation.

Say I have $2k$ matrices $M_{a_1b_1}$, $M_{a_2b_2}$,..,$M_{a_kb_k}$ and their negatives. Here $M_{a_ib_i}$ is such that it has $0$ everywhere except that it has $1$ at $(a_i,b_i)$ and $(b_i,a_i)$ ...
0
votes
0answers
13 views

Can variance be replaced by absolute value in this objective function?

Initially I modeled my objective function as follows: argmin var(f(x),g(x))+var(c(x),d(x)) where f,g,c,d are linear functions in order to be able to use mixed integer linear solvers, I modeled the ...
0
votes
0answers
39 views

Help to find the dual of a linear programming problem [on hold]

Can someone help me to solve this problem that ask to find the dual of this linear program problem: I'm using the Linear Programming: Foundations and Extensions for studying, but it's not helping ...
1
vote
1answer
33 views

Warm start of simplex algorithm after update of constraint matrix

Assume we found an optimal solution $\mathbf{x}_1$ of the linear program \begin{gather} \max \mathbf{n}^T\mathbf{x}\mbox{ s.t. }A\mathbf{x} \leq \mathbf{b}\tag{1} \end{gather} using the simplex ...
3
votes
2answers
39 views

Faster Algorithms for Convex Hulls

I was interested in the following: Given two polyhedra $P_1, P_2$ specified in the form: $$ P_1 = {x : A_1x \le b_1 } $$ $$ P_2 = {x : A_2x \le b_2 } $$ Whereas $ x \in R^n$ and $b_1, b_2$ are ...
0
votes
0answers
35 views

Find all answers to a Mixed-Integer-Linear-Program using branch and bound?

I am trying to solve a MILP which might have multiple answers (all give the same value for objective function). Is a branch and bound based algorithm able to find all solutions? Is it possible to ...
0
votes
2answers
33 views

Linnear programming system of equations and restrictions

While doing a linnear programming problem, i came with this system of equations of 10 variables, and 7 restrictions (7 equations and 10 inequalities). The objtective is to minimize the function: ...
0
votes
2answers
26 views

How do you find redundant constraints for a feasible region?

I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm only trying to find the non-redundant constraints that define a feasible region (i.e. I ...
0
votes
1answer
27 views

Integer Points in Simplex

Let $$A_w(d,q):=\left\{{\bf k} \in \mathbb{N}_0^d: \sum_{j=1}^d w_j k_j \leq q\right\}$$ denote the number of non-negative integer points in the $\ell_1$-ellipse with semi-axes of length ...
0
votes
1answer
19 views

Is it linear or nonlinear, time-invariant or time-varying?

The equation of motion can be expressed as $M(t)\ddot{q}(t) + D(t)\dot{q}(t) + K(t)q(t) = f(t)$ where $q(t)$ is the defection, $M(t)$, $D(t)$, and $K(t)$ are the mass, damping, and stiffness ...
0
votes
0answers
16 views

Linear Programming: Assignment Problem with additional constraints

I have an LP model that assigns events to dates using an assignment model, where each event has a benefit value and we maximize the sum benefit value. There is a binary decision variable for every ...
1
vote
1answer
34 views

How many solutions does a LP problem with the graphical method have?

are following statements correct: 1) when solving an LP problem with the graphical method and the acceptable range is bounded. Then there is always a unique solution. in addition, the unique ...
0
votes
0answers
18 views

Extreme pts of a polyhedral feasible set

Consider a linear program $\min \{c^T x:Px=q,x\geq 0 \}$, where $P \in \mathbb{R}^{m \times n}$. $x\geq 0$ means each component of $x_i$ of x is nonnegative. The feasible set is $\{x:Px=q,x\geq ...
0
votes
1answer
22 views

Measuring rotation and translation differences between two matrices

I am developing a docking application in which I want to have for every step the difference between the target transformation matrix and the user's transformation matrix. Now I don't have any problem ...
0
votes
1answer
23 views

When solving a system of equations for a game theory question, can the solutions be negative?

I have a homework question on solving a game matrix geometrically. $m =$ $\begin{bmatrix}1 & 11\\7 & 2\end{bmatrix}$ (after adding the constant $k$ to ensure it's a positive matrix) The ...
1
vote
0answers
24 views

Solving linear constrained optimization problem

So I have the following constrained optimization problem to optimize a circuit (electrical engineering) that I am working on: Minimize the following expression (power dissipation): $$I_{B1}(V - C_1) ...
0
votes
1answer
29 views

Placing Circles Onto Lines For Optimality

Suppose you have a yet to be determined number of vertical lines with length 50 on which you'd like to place as many circles as you can. Each circle is 10 units in diameter and its outside edge must ...
0
votes
2answers
44 views

Write a linear equation that represents this scenario.

Emma is planning her summer and would like to work enough to travel and buy a new laptop. She can earn 90 dollars each day, after deductions, and she can work a maximum of 40 days in July and August, ...
0
votes
0answers
34 views

Optimal solution in which only one decision variable is non-negative

Given the following LP: \begin{align} \max\quad & 29x_1 - 4x_2 + 5x_3 + 7x_4\\ \mathrm{s.t.}\quad & 4x_1 - x_2 + x_3 = 1\\ &3x_1 - x_2 + x_4 = 1 \end{align} show that an ...
0
votes
1answer
24 views

Linear/Integer programming reference request

There are a few other similar questions out there, but I think mine is not a duplicate because I am looking for a different kind of references than most people. I am primarily a discrete ...
0
votes
1answer
23 views

The number of solutions of a binary integer programming problem

A 0-1 linear programming problem with three variables can have at most $3! = 6$ acceptable solutions? Is this right or wrong?
1
vote
1answer
16 views

What is the Dual of this particular Linear Program ( I get a weird Dual)

maximize $x_1-2x_2+3x_3-4x_4$ s.t. $x_1+x_2+x_3+x_4 = 20$ $x_1,x_2,x_3,x_4\geq 0$ The Dual can be found by transposing the constraint matrix and interchanging the objective function with 20 in ...
1
vote
1answer
28 views

L1 minimization linear programming

So suppose we want to minimize the sum of the absolute errors $\sum\limits_{i=1}^m |b_i - \sum\limits_{j=1}^n a_{ij}x_j|$ with respect to $x_k$ where $k=1,...,n$ So to formulate this as a linear ...
0
votes
0answers
16 views

Solving linear objective functions with linear and non linear constraints

Is it possible to use Matlab commands intlinprog and fmincon to solve a linear programming problem with a linear objective ...
0
votes
0answers
28 views

Solving a Linear Programming Problem

I came across this but have no clue on how to go about it cause all I see are the constraints. Question A dictator seizes power in a small state and proceeds to plan the economy and labour forces. ...
0
votes
0answers
18 views

solve least absolute deviation with non-negative constraints

We have an $m\times n$ matrix $A$, a vector $x$ of length $n$ and a vector $y$ with length $m$. We want to minimize the absolute deviation $|y-Ax|$, with all $x \geq 0$. What kind of toolkit should we ...
0
votes
0answers
28 views

When exactly are quadratic objective functions polynomial time solvable

I'm considering quadratic programming problems of the form: $$ \max x^tQx+Bx$$ subject to the linear constraint $$ Ax \le b $$ I read that if is the case that $$ x^tQx + Bx \ge 0 \ \forall x$$ or ...
0
votes
0answers
30 views

formal definition of a linear programming formulation

Despite having done operations research for several years, and being familiar with linear programming formulations, I am having difficulty giving a formal definition of what it means for something to ...
1
vote
1answer
18 views

Is it possible to make a linear reformulation?

The question is what to do when we have a product of the three variables, quite different in their nature. One is binary, the second is real, and the third is from a discrete set of rational numbers. ...
0
votes
0answers
28 views

Solving large system of Linear equations

I am trying to solve an optimization prob of the below form: $$ \min \sum_{k=0}^{n} p_k$$ subject to : $$0 \leq p_k \leq p_{\max}$$ $$ g_k p_k \leq I_t$$ $$g_k p_k - \eta_k \sum_{j \neq k} p_j ...
0
votes
1answer
47 views

Deduce LP maximization problem from sensitivity analysis

I have the answer to and the sensitivity analysis for a LP maximization problem. (See picture) http://postimg.org/image/xs4iowbrj/ How can I deduce the original LP problem? I have figured out this: ...
0
votes
1answer
23 views

How to find the point in convex set $C$ that is closest to $y\notin C$?

How to find the point in convex set $C$ that is closest to $y\notin C$? $C=\{ x\in \mathbb{R^2}:(x_1-1)^2+(x_2-1)^2\le1 \}$ and let $y\notin C $ but $y\notin \mathbb{R^2} $.
0
votes
2answers
24 views

Single nonzero value constraint formulation in linear programming problem statement

I'm trying to write a linear programming problem statement. Values of the solution vector have a bound constraint: $0 \leq x_i \leq 1$. Another constraint is that if we take a predefined subset of ...
1
vote
0answers
51 views

Can this be expressed in terms of linear constraints?

I'm attempting to find a matrix $X$ that minimizes some function $f(X)$ subject to the constraint that $$ X=W A Z $$ where $A$ is a given non-negative matrix with rows that sum to 1, and $W$ and $Z$ ...
0
votes
1answer
32 views

Use graphical methods to solve the linear programming problem. Maximize:

Use graphical methods to solve the linear programming problem. Maximize: $z= 4x+2y$ subject to : $x-y\le 7$ $19x+12y\le 228$ $18x+18y \le 324$ $x\ge 0,y\ge 0$ the max is ?? when x= ?? and ...
1
vote
1answer
25 views

best method for solving fully degenerate linear programs

I am looking for efficient computational methods for solving a class of linear programs whose right hand side is zero: $$ \min c^T x \qquad\text{ subject to }\qquad Ax\ge 0 $$ What is the best ...
1
vote
1answer
33 views

Shortest Path Length as mathematical function/expression

I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities. The degree of any node should be at least 3. The shortest path length ...
5
votes
1answer
60 views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
3
votes
2answers
106 views

a vector inequality and combinatorics related question

This question is a similar restatement of this question which has been recently closed. Let $$A=\{\ (x,y,z)\in\mathbb{N}^3\ |\ 0\leq x,y,z\leq7\}$$ and $$B\subset A \text{ with } ...
0
votes
0answers
32 views

Fundamental Theorem of Linear Programming

I'm reading Dan Stefanica's book "A Linear Algebra Primer for Financial Engineering", which says in pp 92, $\S3.2$ that "...the Fundamental Thorem of Linear Programming, which, informally speacking, ...
0
votes
1answer
22 views

linear programming : Absolute value in constraint in mathematical model

I have a model have an constraint with evaluation of absolute value , a example can be: function objective : $\max \sum(x_i)$ statement: $x_i\geq |(y_i-t_i)|$ for all $i$ but value absolute ...
0
votes
2answers
32 views

Simplex algorithm with initial negative slack variables

I have the following LP problem: $$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x & \le 3\\ & & x & \ge 3\\ & & -x + 2y & \le ...
1
vote
1answer
198 views

What kind of a problem is this?

The problem can be stated as: I have $m$ liquids ($A_i$ is the amount of the $i$-th liquid) and $n$ tanks ($x_j$ is the volume of the $j$-th tank), and the task is to find the best way to ...
-1
votes
1answer
33 views

Linear equations problem [closed]

The Marshall County trash incinerator in Norton burns 10 tons of trash per hour and co-generates 6 kilowatts of electricity, while the Wiseburg incinerator burns 5 tons per hour and co-generates 4 ...
0
votes
0answers
15 views

How to Adequately Implement Phase I of Two-Phase Simplex Algorithm on a Computer with Floating Point Error

I'm currently trying to write some code that implements Phase I of the two-phase Simplex Algorithm described here: http://www.statslab.cam.ac.uk/~ff271/teaching/opt/notes/notes8.pdf In order to test ...
1
vote
1answer
41 views

Tutorial for Simplex Method with No Slack Variables

I found a nice tutorial here http://www.math.ucla.edu/~tom/LP.pdf for applying the Simplex Method to problems of the form: maximize $c^T x$ with the constraints $Ax\leq b$, $x_i \geq 0$. It suggests ...
0
votes
1answer
53 views

Edges of Hypercube

I may have some problem with this: Given a linear program $$\max{4x_1 + 2x_2 + x_3}$$ under the constraints $$ x_1 \le 5 $$ $$ 4x_1 + 1x_2 \le 25 $$ $$ 8x_1 + 4x_2 + 1x_3 \le 125 $$ $$x_1,x_2,x_3 ...
0
votes
1answer
37 views

how to check whether feasible solutions exist for linear programming

For a linear programming problem, how to decide whether there exists a feasible solution without solving it? For Ax<=B, is there any sufficient and/or necessary condition represented by A and B to ...
0
votes
1answer
32 views

Solution of linear inequality

I have the following system of linear inequality on $x_1, x_2, \dots, x_n$, $x_i \in \mathbb{R} \; \forall i$ $x_i - 2x_j < b \; \forall i, j$ The right hand side of the inequality ($b \in ...