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

learn more… | top users | synonyms

0
votes
0answers
22 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 ...
3
votes
1answer
2k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
1
vote
1answer
25 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
37 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 ...
2
votes
2answers
404 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
1
vote
1answer
374 views

Binary constraint integer programming problem

Hi I have a question to the folowing question: Explain how to use integer variables and linear inequality constraints to ensure: A) let x and y be integer variables bounded at 1000. How can you ...
1
vote
2answers
690 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
0
votes
0answers
34 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 ...
4
votes
1answer
2k views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ ...
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: ...
1
vote
1answer
291 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
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
0answers
28 views

Reason for use $L^2$-Norm instead of $L^1$-Norm in Optimization [closed]

In optimization we use $\min\; \Vert Ax-b\Vert_{2}^2$ instead of $\min\; \Vert Ax-b\Vert_{2}$ because second is not differentiable. But I am looking for a clean and mathematical reason for this. And ...
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
1answer
35 views

How is the pivot chosen for the symbolic weights for the Cassowary algorithm?

I am trying to understand The Cassowary Linear Arithmetic Constraint Solving Algorithm, and I am having trouble understanding symbolic weights, starting in section 2.3. Working through the example, ...
0
votes
2answers
994 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
4
votes
2answers
3k views

Solving $Ax=b$ under $L_1$ $|Ax-b|$ minimization

I would like to solve a linear system $Ax = b$ under the $L_1$ norm constraint $\min(|Ax-b|)$. All that I can find about $L_1$ minimization is a way to minimize $|x|_1$ subject to $Ax=b$. I wanted to ...
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 ...
0
votes
1answer
364 views

Formulate model

Carter Enterprises is a soybean trading company. Once a month a representative attends a commodity sale where he either buys or sells soybeans in bulk. Carter uses a local warehouse for storing ...
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
16 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 ...
1
vote
1answer
1k views

Linear programming: basic solutions?

http://www.math.toronto.edu/kergin/236_t1_2.pdf For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
0
votes
1answer
22 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) ...
1
vote
1answer
978 views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
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
1answer
525 views

finding the minimum number of lines to cover all zeros in an assignment probem

I have been trying to follow the following steps to find the minimum number of horizontal and vertical lines that cover all the zeros in an assignment problem using Hungarian method: Tick all ...
5
votes
1answer
59 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 ...
0
votes
2answers
43 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
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
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
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?
0
votes
1answer
312 views

Multiple Choice Knapsack Problem (MCKP) where one class requires more than one item

I have the following problem of which I am attempting to find a near optimal solution: I have one knapsack which can hold a maximum weight. I must select exactly one distinct item from a number of ...
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
26 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 ...
1
vote
1answer
24 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 ...
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
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
29 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
1answer
345 views

Linear Programming formulate if then constraint

Consider an LP for which you want to add the restriction that Only if $x_1\geq 3$ then $x_2$ and $x_3$ are allowed to be larger than $0$; otherwise $x_2$ and $x_3$ are $0$. Demonstrate how to ...
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 ...
4
votes
1answer
2k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
0
votes
2answers
197 views

Transportation problem in supply chain

I understand how to solve transportation problem with only members in the chain, but how can I solve the transport problem with multiple members in the chain? Thank you.
3
votes
1answer
316 views

Converting if else constraints into linear ones

I have the following two constraints: $$ x_1 \leq x_2 \leq x_3 \qquad \mbox{if } x_1 \leq x_3 \\ x_1 > x_2 > x_3 \qquad \mbox{otherwise} $$ Is there a way to get rid of the two conditions and ...