Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
-1
votes
1answer
620 views

Knapsack problem

Knapsack problem we can solve several methods: dynamic programming branch and bound greedy method genetic algorithm Brute force Heuristic by the value / size Which of these methods gives accurate ...
-1
votes
1answer
182 views

LP problem: Does ratio of capacity refer to volume? Weight?

I have to set up an LP problem based on this situation below: What I tried: Let $x_{i,j}$ denote amount of loot i in hold j for i = 1,2,3 corresponding to materials, gold and spice for j = 1,2,3 ...
-1
votes
1answer
227 views

Find all the points satisfying the Fritz John conditions

Consider the problem $$\min \>x^2+y^2 $$ $$s.t.\> x^2-(y-1)^3=0$$ Find all the points satisfying the Fritz John conditions Solution The FJ conditions are $$2x+\mu_1 2x=0$$ $$2y-\mu_1 3(y-1)^...
-1
votes
1answer
140 views

Linear programming problem-optimal solution

I'm having the following linear programming problem: $$\begin{align} \max \quad & 2x_{1}+6x_{2}+3x_{3}, & \\ \text{s.t.} \quad & -3x_{2}+a x_{3} \geq2, \\ & x_{1}+5x_{2}+2x_{3} =2, \\ &...
-1
votes
1answer
43 views

Need help formulating this linear program [closed]

A company's pension fund manager must invest a maximum of $300,000 in bonds and stocks in order to obtain the highest possible return on investment. However, in order to obtain a risk-adjusted ...
-1
votes
1answer
32 views

Combination of AND OR in Linear Programming

I have three binary variables: $x,y,z$. I want to define $U$ as follows: $$U = x \wedge (y \vee z)$$ Following this, I have already tried defining $$yz = y \vee z$$ and then, doing $$U = x \...
-1
votes
1answer
39 views

Write IF THEN constraint in Linear Programming for Non Binary Decision Variable

$ x_{t} $ is a decision variable bounded by some constraints and $t=1,2,3..24$ If at some point in t, the value of $x_{t}$ changes then the value must not change for ATLEAST the next 3 hours. After ...
-1
votes
2answers
70 views

Linear Programing: Set binary variable 1, if two variables are not equal

I guess I have a simple problem, but I can't find a fitting solution. I have a certain amount periods $D$, and every period is described by the decision variable $X_d$. What I want to do is set a ...
-1
votes
2answers
67 views

How to write the optimization constraint of the following problem

$A$ is an adjacency matrix and $W$ is the weight matrix. So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{...
-1
votes
1answer
30 views

Confusion about the dual problem in linear programming [closed]

Why do books usually define the dual problem only for a standard min problem or standard max problem and not both? Can the same procedure that converts a standard max problem into its dual be used to ...
-1
votes
1answer
40 views

Reducing data sparsity in linear integer programming

I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix ...
-1
votes
1answer
55 views

Satisfiability of inequality array with binary and arithmetic operators

I have a problem as follows. Really appreciate if anyone can give me some suggestions. I have $4000$ binary variables $\{x_0, x_1,...x_{3999}\}$ and $4000$ inequalities which have both binary ...
-1
votes
1answer
133 views

transforming an absolute value objective function into a linear programming model

I am having a little trouble converting this problem into a linear programming model and how it affects the constraints. max-z = |2x1 - 3x2| s.t. 4x1 + x2 <= 4 2x1 - x2 <= 0.5 x1, x2 >= 0
-1
votes
1answer
62 views

constrained assignment optimization problem

I have a large number of objects $r$, in a store, $M=\{r_1, r_2, …., r_N\}$, with size $D$. The objects have different lengths $l_i$ and selling prices $ρ_i$, $ρ_iϵ[0,1]$, such that $\forall r\in M$: $...
-1
votes
1answer
55 views

Finding the number of solutions.

$$x_1+x_2+...+x_p+y_1+y_2+...+y_q \ge X$$ where $$x_1,x_2..x_p, y_1,y_2..y_q$$ are all non-negative integers, $$x_1..x_p\le a$$ $$y_1...y_q\le b?$$ The original problem is "You are given $N$ ...
-1
votes
1answer
65 views

How to represent in Linear Programming (equations)?

Suppose $i$ varies from $0$ to $4$. $A_i$, $S_i$, $E_i$ are binary variables. Now, if $S_1=1$ and $E_3=1$, then how to make $A_1=A_2=A_3=1$ and $A_0=A_4=0$ using linear equations?
-1
votes
1answer
87 views

Silly question about system of inequalities

I need a confirmation Let's say I have a system of inequalities $$ \left\{ \begin{array}{l} Ax \leq b \\ x \geq 0 \end{array} \right. $$ $A \in \mathbb{R}^{m \times n}$ , $x \in \mathbb{R}^{n \times ...
-1
votes
2answers
104 views

How to solve this question by the two-phase simplex algorithm?

A clever but ethically corrupted mathematics student used to sell assignment solutions to her lazy fellow students. The student, however, learned that she can make much more money by charging the ...
-1
votes
1answer
37 views

Question about simplex method mentioned in A. Schrijver's book

I am reading section 1 of chapter 11 of A. Schrijver's book Theory of Linear and Integer Programming. He frist introduces how to find an optimal solution of LP problem $$\max\{cx|Ax\le b\}$$ if you ...
-1
votes
1answer
1k views

Linear Programming - The Big M Method - Proof questions [closed]

I'm having difficulties on answering the following questions (first time I'm trying to prove something), any help would be awesome! Thanks in advance. Q: It is possible to combine the two phases of ...
-1
votes
1answer
2k views

Solve a linear programming minimization problem with greater-than-equal sign in the constraints using the Simplex method

I need to solve the following linear programming minimization problem using the Simplex method: ...
-1
votes
1answer
30 views

How can I derive the following Linear Programming

How can we derive the dual problem? max$_{x} v^{T} x$ subject to $w^{T} x \le W, 0 \le x_i \le 1 ( i=1,...,n )$ where $ v \in \Bbb {R}^{n}, w_i \in \Bbb {R}^{n} $ and $ W \in \Bbb {R} $
-1
votes
1answer
164 views

Finding an $O(n \log n)$ time algorithm for an optimization problem

Consider the following optimization problem: Let $n$ be even and let $c$ be a positive vector in $\mathbb{R}^n$. Find $$\min\left\{c^T x : (x \geq 0) \text{ and } \left(\forall S \subseteq [n], \ |...
-1
votes
1answer
924 views

How to express $y = x\ \mathrm{mod}\ 2$ as an ILP?

Using the signed modulo operation: $(x\ \mathrm{mod}\ 2) = \begin{cases} 0\ \mathrm{if}\ x\ \mathrm{is\ even} \\ 1\ \mathrm{if}\ x > 0\ \mathrm{and}\ x\ \mathrm{is\ odd} \\ -1\ \mathrm{if}\ x &...
-2
votes
2answers
154 views

Is the area of linear programming dead right now? [closed]

By dead i mean not much/completely no research there . Is the area of linear programming dead right now? If it is not dead, what are the active area called for example except computer science?
-2
votes
1answer
23 views

Why do we call Basic solution (linear programming), any reason for that ?? [closed]

I'm just curious that why do we call such a solution with some property, a "basic" solution. I would like to know the background. Thank you in advance.
-2
votes
1answer
160 views

Linear programming solve minimization as maximization

Given the following problem: $$max \ x_1 + x_2\\ s.t. \ x_1 \ge 0\\ x_2 \ge 0 \\ x_2 - x_1 \le 1 \\ x_1 + 6x_2 \le 15 \\ 4x_1 - x_2 \le 10$$ The result is 5 as shown here: https://imgur.com/iLkyXlc ...
-2
votes
1answer
39 views

Linear Programming query

Rewrite: If $x_1=1$ then $x_2+x_3+x_4+x_5=0$ in linear programming if variables $x_1,x_2,x_3,x_4,x_5$ are binary? Edit:Sorry the sum of $x_2,x_3,x_4$ and $x_5$ should equal $0$. I tried re-writing ...
-2
votes
1answer
324 views

Why does COIN-OR CBC Solver have both Continuous Solution Unbounded and Dual Infeasible exit statuses?

I am working with COIN-OR CBC solver. I understand that Primal unbounded is dual infeasible. After seeing the exit statuses for CBC Solver, I came to know that both these conditions have their own ...
-2
votes
1answer
98 views

Modelling Problem in Linear Programming Standard Form

I'm having a hard time setting this up, so that's what I need help with. The solving I understand. We’re making a drink with the following requirements: at least 500 calories, at least 20 mg. of ...
-2
votes
1answer
132 views

linear programming - how to write standard form

i've created a small linear optimization modell (simplex) in excel. it assigns products to shelfs and minimizes the total distance. My math skills are rusty. how do i write this LP-Modell in the ...
-2
votes
1answer
61 views

Inversion of a matrix in a system of linear inequalities

I would like to know if someone knows sufficient conditions on $A\in\mathbb{R}^{n\times n}$ and $b\in\mathbb{R}^{n}$ such that for all $x\in\mathbb{R}^{n}$: $$Ax\leq b \Rightarrow x\leq A^{-1}b \text{ ...
-3
votes
1answer
42 views

Then the dimension of $S$ [closed]

Let the convex set $S$ be given by the solution set of the following system of linear inequalities in sixteen variables such that \begin{alignat}{2} \sum _{j=1} ^4 x_{ij}&=3, &\quad i&=1,...
-4
votes
1answer
112 views

Linear/Integer programming for discrete mathematicians

I am primarily a discrete mathematician (designs/finite geometries), and I've been using Gurobi to solve some integer programming problems related to my research. While I'm comfortable using the ...
-4
votes
1answer
91 views

Affine Scaling Approach question [closed]

Let's consider the following LP. $$ \max z = 2x_1 + 3x_2 + x_3 $$ $$ \text{s.t. } \begin{align} \\ \\ \\ & 3x_1 + 2x_2 + 4x3 \le 7 \\ & 5x_1 -2x_3 \ge 1 \\ & x_1 + 2x_2 + x_3 = 2 \\ &...
-5
votes
2answers
234 views

linear programming question! [closed]

A tea emporium offers two 100g packs of tea for sale, standard and luxury, and both are blends of tea varieties. Per pack the standard blend uses 10 grams of Assam tea, 10 grams of Darjeeling tea and ...