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

learn more… | top users | synonyms

0
votes
0answers
18 views

Solving simple LP problem with Lagrange multipliers

Hi just as a test I'm trying to solve the following LP with Lagrange multipliers. $min -x_1$ $s.t$ $x_2 \leq 1 - x_1$ $x_1, x_2 \geq 0 $ I add slack variables to have a equality constrained LP ...
0
votes
0answers
14 views

Scalarization of multi-objective optimization problem (weighted sum approach)

I have an objective function where I try to minimize the quantity of bandwidth used in a network (Mbps units) - first part of the function -, minimize the CPU used in different nodes in the network (...
1
vote
1answer
21 views

Degenerate solution in linear programming

How can I determine if a solution in a linear programming problem is degenerate without I use any software or the graphical display of the solution; For example in the model: $$\max\{2x_1 + 4x_2\}\\\...
-1
votes
0answers
14 views

What determines the convergence time of a linear program?

I was wondering what are the properties of an LP problem or its the objective function that determine how fast CPLEX finds an optimum. To be specific, given a classical linear programming problem ...
0
votes
1answer
27 views

He makes $3$ products for his shop: large bowls, small bowls, and pots

He makes $3$ products for his shop: large bowls, small bowls, and pots. Each large bowl uses $3$ pounds of clay and $6$ fluid ounces of glaze. Each small bowl uses $2$ pounds of clay and $6$ fluid ...
0
votes
2answers
31 views

Linear equation in n variables with non negative solution

The problem is that given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers ...
0
votes
0answers
29 views

Using the simplex method to find the minimum cost

A local food bank puts together complementary gift packages for its donors during their pledge drives. The bank's costs for each package are $\$4$ dollars for the Bronze level package, $\$7$ dollars ...
0
votes
0answers
29 views

silver bronze linear optimization

A non-profit offers crafts complimentary gift packages for its donors. The non-profit costs for each package are \$4 for the Bronze level package, \$7 for the Silver level package, and \$9 for the ...
1
vote
1answer
35 views

Maximization problem setup and analysis

So, I needed help in setting up the following: A coffee company sells two types of breakfast blends. They have on hand $132$ kg of dark roast and $84$ kg of hazelnut. One breakfast blend will ...
0
votes
1answer
70 views

Does this linear system have a single solution

Given unknown $x_1>0$, $x_2>0$, $x_3>0$, $x_4>0$, and known $y_1>0$, $y_2>0$, $y_3>0$, $y_4>0$, $$ \begin{cases} x_1+x_2=y_1 \\ x_1+x_4=y_2 \\ x_3+x_2=y_3 \\ x_3+x_4=y_4 \end{...
0
votes
2answers
37 views

Break even methodology

Southeast Moldings molds plastic handles which cost $\$1.00$ per handle to mold. The fixed cost to run the molding machine is $\$3,640$ per week. If the company sells the handles for $\$4.00 $ each, ...
0
votes
0answers
19 views

Geometric interpretation of linear programming dual

Is there a geometric interpretation of the linear programming dual in terms of the primal? I feel like without some sort of intuition of it, I don't truly understand it.
0
votes
2answers
84 views

Tableau and Simplex Method - No Calculator

A non-profit offers crafts complimentary gift packages for its donors. The non-profit costs for each package are \$4 for the Bronze level package, \$7 for the Silver level package, and \$9 for the ...
3
votes
2answers
33 views

L1 minimization problem with nested sums as LP problem

I've been trying to solve this problem but I have an issue with the fact that there is a sum under each absolute value. I'm trying to convert this minimization problem (with respect to $x, y_1, \dots,...
0
votes
1answer
36 views

Why isn't Linear Programming less convoluted? [Soft Question]

Just a quick question. So I'm taking a course in linear optimization, and one of the things that we're going over obviously is the simplex method. I just started the class so I may not be seeing the ...
0
votes
1answer
29 views

Linear program with ceiling or floor functions

Is it possible to solve a linear program where constraints have ceiling or floor functions applied to variables (with maybe some constants)? For instance: $$\lceil (x_1 + a)/b \rceil + \lceil (x_2 + c)...
1
vote
0answers
32 views

Checking feasibility of a system of inequalities with scipy

I have a set of pairwise constraints, like this: a > b, b > c, c > a and need to check if they are satisfiable (in the example above, they are not). ...
0
votes
0answers
39 views

Finding shortest vertical segment connecting two sets of intersecting half-planes

Consider two sets of $n$ half-planes each. Denote the sets by $A$ and $B$. How can we find a vertical segment $s$ of a minimum length such that the upper end of $s$ is in the intersection of $A$ and ...
1
vote
1answer
41 views

Linear programming with a product term in the objective function

The title might sound a little weird. I actually want to ask if this problem can be solved as a LP. And if so, how to convert the product term? set $P=\{1,2,3,\ldots,n\}$ for index $i$. Variables $...
1
vote
1answer
24 views

Existence of solution to underdetermined linear system with variable coefficient matrix.

I'm trying to think through a network flow problem, and while I could probably shuffle this into a form that a linear programming method would work, it feels like there ought to be something more ...
0
votes
1answer
24 views

All-sizes Network Simplex

I am currently using Network Simplex to find the min-cost flow to send $x$ units of goods from source $s$ to sink $t$ given a capacitated graph. I would now like to solve the problem for all $x \in [...
2
votes
1answer
22 views

Model cost for a state change in an integer program

I have a problem involving tool selection I am trying to model right now. (I am fairly new to this). I have a series of manufacturing operations I need to perform for $i \in \{1,\dots,n\}$. Each ...
0
votes
1answer
20 views

Will the slack variables always have coefficients of zero in the objective function?

I've been following this video: https://www.youtube.com/watch?v=M8POtpPtQZc Will the CBi values (slack variable coefficients) ever not be zero? When?
2
votes
2answers
70 views

How to covert min min problem to linear programming problem?

I have the following problem: set $P=\{1,2,3...,n\}$ for index $i$, set $K=\{1,2,3,...,m\}$ for index $k$. Value $B_i^k$ is indexed by both $i$ and $k$, while value $l_i$ is indexed by only $i$. Here ...
0
votes
1answer
20 views

Convert this problem into linear programming format

This problem is from the book Luenberger "Linear and Non Linear Optimization". I am facing difficulty with this problem. I am trying to follow this logic - Let $t = \max (c_1^Tx+d_1,....,c_p^Tx+d_p)$...
2
votes
2answers
56 views

Sensitivity analysis in linear programming

Could someone please explain in detailed steps how to apply a sensitivity analysis to such problem: $$maximize \ \ 2x_1 + 3x_2 \\ s.t. \ \ 4x_1+3x_2≤600 \\ 2x_1+2x_2≤320 \\ 3x_1+7x_2≤840 \\ x_i≥0$$ ...
0
votes
0answers
17 views

Solve $\max_{\lambda} \mathrm{sum} (\lambda \vec{u} \geq_c \vec{v})$

Let $\vec{u},\vec{v} \in R^n$ be known vectors. I want to find out the optimum scalar multiplier $\lambda$, to maximize the number of elements in $\lambda \vec{u}$ which are above $\vec{v}$. In other ...
1
vote
3answers
78 views

Binary integer variables in linear programming

Could someone please explain the concept of switch variables (binary integer decision variables) in linear programming? This example has two alternative constraints $$\begin{array}{ll} \text{...
0
votes
0answers
15 views

Solve $\max_X \mathrm{sum}(AXB \geq \gamma)$, with $X$ being a permutation matrix

I have a problem to find the best permutation matrix $X \in \{0,1\}^{n \times n}$, which would maximizes the number of elements in $AXB$ which are above a certain positive number $\gamma$. In other ...
1
vote
0answers
17 views

Find optimum diagonal matrix $D$ to maximize $ADB$ above a threshold $\gamma$

I have a problem to find the optimum diagonal matrix $D$, which would maximizes the number of elements in $ADB$ which are above a certain positive number $\gamma$. In other words, the problem is ...
0
votes
0answers
14 views

Finding Dual of non-standart programming problem

I am working in optimization field. My programming problem is not of the standart form, however it is convex. Objective is nonlinear but concave (log of product). I do maximization. Constaints: ...
0
votes
0answers
18 views

Find permutation matrix $X \in \{0,1\}^{N \times N}$ in order to make $XAX \geq_c B$

I need to solve a problem to find out the best permutation matrix $X \in \{0,1\}^{N \times N}$ which would maximize the number of elements in matrix $XAX$ which are above (component-wise) matrix $B$ ...
1
vote
1answer
39 views

Prioritized solution of a linear system subject to inequality constraints

Consider the following linear system \begin{equation} y = A_1 x_1 + A_2 x_2 \end{equation} subject to the linear constrains \begin{equation} C_1 x_1 + C_2 x_2 \leq d \end{equation} I am looking ...
0
votes
0answers
23 views

simplex method for minimal

Use the simplex method to solve the following linear programming problem. Find y1≥0 and y2≥0 such that 2y1 + 2y2 >= 13, y1 + 2y2 ≥13​, and w=3y1 +18y2 is minimized. I'm trying to find the minnimum of ...
0
votes
1answer
35 views

simplex method tableau

If I have the matrix: x1 x2 s1 s2 s3 z 1 4 1 0 0 0 | 12 2 5 0 1 0 0 | 2 1 3 0 0 0 1 | 4 ---------------- -2 -1 0 0 0 1 | 0 Then, where x1 is the row of 1, 2, 1....x2 is the row of 4, 5, 4.......
0
votes
1answer
26 views

Determine all solutions of a linear program

I have the following linear optimization model: $$\begin{array}{ll} \text{maximize} & x_1 + 2 x_2\\ \text{subject to} & 3x_1+2x_2 \leq 12\\ & x_1+3x_2 \leq 9\\ &2x_2\leq2\end{array}$$ ...
0
votes
0answers
27 views

Can a binary integer linear program be converted to a linear program?

I need to solve the following binary integer linear program: $$ \max \textbf{c}^T \textbf{x} $$ Subject to: $$ \textbf{Ax} \le \textbf{b} $$ Where $ \textbf{b} \in \mathbb{Z}^n $, $\textbf{A} \in \...
1
vote
1answer
73 views

Can this optimization problem be solved?

I am working on an optimization problem but I am not sure if the problem can be formulated as an integer programming problem. Assume the cost minimization problem for a set of subscribers and ...
0
votes
0answers
31 views

Negative bounds on variables in Linear Programming formulation

I am new to optimization theory and encountered the following problem: I am reviewing a formulation for a network problem that is fed into a mathematical solver and I noticed that on the "bounds" ...
0
votes
1answer
30 views

Cubic Polynomial fitting with defined ranges for coefficients

Is there a way, given a set of values $(x,y)$, to find a cubic polynomial $f(x)$ that fits the values? My cubic polynomial is defined as $c_0 + c_1x +\frac {1}{2} c_2 x^2 +\frac {1}{6}c_3 x^3$ ...
0
votes
1answer
25 views

Linear Programming: Transportation Problem with alternatives

Could someone please explain how to solve such task by linear programming: Let's say there is a starting point $A$ and two end points $B$ and $C$. $A$ is connected to $B$ and $C$ and the connections ...
0
votes
1answer
9 views

Linear Programming: LP-Model

Let's say there are 2 types of TV shows. The first one S1 is usually watched by 2 women and 1 man. The second one S2 is watched by 1 women and 3 men. A company wants to show commercials to reach at ...
0
votes
0answers
13 views

how to calculate slack(u,v) in the Edmond's minimum weight matching algorithm (u and v are vertices of a graph)?

I am trying to execute the Edmond's minimum weight matching algorithm. As a reference, I am using a book titled "Combinatorial Optimization Theory and Algorithms" by Bernhard Korte and Jens Vygen. The ...
2
votes
3answers
61 views

Problem of Linear Programming, Scilab or Octave

I have to solve this with Octave or Scilab. There's an airplane company with airplanes flying to 3 different destinations (London, Paris, Rome). Schedule of flights ...
1
vote
1answer
34 views

Polyhedron, understanding face vs facet.

I've the two following definitions, for which I was trying to understand the difference. For a given polyhedron $P$ a face $F$ is both $P$ itself or the intersection of $F$ with $P$. A facet is ...
1
vote
1answer
36 views

Show identity using Cauchy-Schwarz' inequality

For $v=(v_1,...,v_n)^T \in \mathbb R^n$ we let $f(v)=|v|^2=v^Tv=v_1^2+...+v_n^2$. Show using Cauchy-Schwarz' inequality: $u^Tv \leq|u||v|$ that, $$ 0 \leq (1-\lambda )f(u)+\lambda f(v)-(f((1-\lambda )...
1
vote
0answers
15 views

Two phase method in linear programming

suppose following tableau came after one iterations in first phase of a two phase method problem, here $s_1$ is a surplus variable and $s_2$ is a slack variable $w$ is a artificial variable. i tried ...
4
votes
5answers
101 views

Feasible point of a system of linear inequalities

Let $P$ denote $(x,y,z)\in \mathbb R^3$, which satisfies the inequalities: $$-2x+y+z\leq 4$$ $$x \geq 1$$ $$y\geq2$$ $$ z \geq 3 $$ $$x-2y+z \leq 1$$ $$ 2x+2y-z \leq 5$$ How do I find an interior ...
0
votes
1answer
16 views

Formulating a problem involving sets with ILP

Consider set $\mathcal{G} = \{G_1, \ldots, G_K\}$. We are given $\mathcal{A}_i \subset \mathcal{G}$, $i \in \mathcal{N}= \{1,\ldots, N\}$ and for each $\mathcal{A}_i$, there is a corresponding cost ...
1
vote
0answers
17 views

Recommend a optimization book with more coding examples?

I am interested in continuous optimization problems. However, I feel it is very difficult for me to understand the classic books such as Convex Optimization or Numerical Optmization. My problem with ...