Skip to main content

Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
0 votes
0 answers
47 views

Objective/Cost Function Normalization (MPC)

I am trying to develop an MPC. In this MPC, I predict the temperature and try to bring the sensor value to the desired setpoint temperature. I predict the temperature in the next 180 minutes for the ...
Clankk's user avatar
  • 1
0 votes
1 answer
82 views

Ensure complete cycle in binary succession matrix LP [PuLP]

I have a set of orders N, for which i have to determine an optimal sequence. I wrap this decision within a binary matrix x[i][j], meaning whether i is succeeded by j. For example [[0 1 0 0] [0 0 1 0] [...
QuestioningPanda's user avatar
3 votes
1 answer
210 views

Warm starting a LP problem with PuLP and Gurobi

I have a set of many similar linear programs (LP). All these LPs have the same objective function, and almost all constraints are the same. The only difference is for one linear constraint $f(x)=a_{i}$...
Quentin PLOUSSARD's user avatar
0 votes
1 answer
90 views

How to set the parameters for GLOP for a DUAL_FEASIBLE case

Now I have a linear programming model, I have tried to formulate this model with or-tools, and then solve it with the GLOP but failed. After reaching the 15-minute time limit, the status of GLOP is ...
Ying's user avatar
  • 105
0 votes
0 answers
62 views

Using docplex with mpmath

In Python 3.10, is it possible to use docplex along with mpmath (https://mpmath.org/), e.g., to compute expressions in constraints and objectives with arbitrary precision?
Stencil's user avatar
  • 101
1 vote
1 answer
156 views

Job Scheduling with Energy Consumption using Linear Programming

I'm looking for some advice for an optimization problem regarding scheduling jobs in a datacenter. So I have a list of jobs and each job has a required time for finishing and a number of cores it has ...
wind.leon's user avatar
2 votes
1 answer
80 views

Reducing optimality to feasibility in non-linear programs

It is well-known that, given a linear program: minimize $c^T x$ such that $A x\leq b$, it is possible to reduce the program to deciding feasibility of the following set of constraints: $Ax \leq b, A^T ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
54 views

Making a batch of related linear problems more efficient

I have a linear system that is of the form $$My = b \\ L \leq y \leq U$$ i.e. all of the $y_i$ are potentially bounded, and there are various linear relationships between them. I want to find the ...
ConMan's user avatar
  • 111
1 vote
0 answers
31 views

Moment based linearization of PDF for LP based optimization

Suppose I’m interested in modeling risk/volatility using the Cauchy distribution and I’d like to optimize some allocations using linear programming. The Cauchy distribution is quadratic in nature but ...
jbuddy_13's user avatar
  • 551
3 votes
2 answers
150 views

Will adding this constraint help my model?

I am solving a maximization problem with continuous variables $x,z\in \mathbb{R}^+$ and binary variable $\delta \in \{0,1\}$. I am maximizing $x$ subject to side constraints and would like to enforce ...
abcd's user avatar
  • 55
1 vote
0 answers
58 views

transform minimize weighted sum of absolute value into a linear optimization

For example, we have an optimization problem $$ \min \sum_{i=1}^{n} |w_{i} - a_{i}| b_{i} \quad \text{s.t.} \quad \sum_{i=1}^{n} c_i w_i = 0 $$ and $a_i, b_i, c_i$ are given. How to convert it into a ...
Pique's user avatar
  • 11
1 vote
1 answer
114 views

Benchmark problems for Benders Decomposition

We are implementing a scheduling model using Benders Decomposition. Does someone know of any existing implementation of Benders or any repositories that contain continuous or integer problems solved ...
Vivek's user avatar
  • 21
0 votes
1 answer
79 views

Sum only over weekend days

I would like to adjust my constraint so that the x are only ever added for the weekend of a week, i.e. days 6,7 and then 13,14 and 20,21 etc.. That would be my previous formulation, but how can I ...
mingabua's user avatar
1 vote
1 answer
98 views

Optimal currency conversion Linear Programming

I have a question about Ex 1.11 of "Linear Optimization" by Bertsimas, Tsitsiklis: Suppose that there are $N$ available currencies, and assume that one unit of currency $i$ can be exchanged ...
Andrew's user avatar
  • 163
0 votes
1 answer
73 views

Problems understanding model notation in LPs

today I came across a paper that uses a type of model notation I have never come across before. These are the objective function and constraints I don't quite understand. I am specifically interested ...
mingabua's user avatar
0 votes
0 answers
127 views

Detect presolve status in pulp model

I am running a model using pulp CBC and have few constraints in the model that may make the model infeasible if wrong input is given to the model. I can see while my model runs that in case of ...
Bhavya Budhia's user avatar
2 votes
0 answers
36 views

Addressing Variable Multiplication in Constrained Infinity-Norm Maximization with Hypercube & Polyhedron Constraints

I am reaching out to this knowledgeable community for assistance with a complex optimization problem that I have been investigating. Here is the formulation of the problem I'm addressing: $$\tag{1} \...
Diego Fonseca's user avatar
0 votes
1 answer
149 views

Maximum Flow Linear Programming

So this is the maximum flow problem and I have two questions here: Why do we write maximize X_jt and why not X_st, since we want to maximize the flow from the source node to the end node? And why do ...
uni_lad's user avatar
  • 39
1 vote
1 answer
72 views

LP: Constraining the maximum of two variables

I have two variables in an LP problem, a and b, both bound in range $(0,1)$ and constrained such that $a+b=1$. So if a=0.25 then b=0.75. I have added a variable t constrained such that $t \ge a-b$ $t \...
jbuddy_13's user avatar
  • 551
4 votes
2 answers
283 views

Column generation: set partitioning vs set covering

I am working with a column generation algorithm and have noticed that convergence is much faster when my master is a set covering problem ($Ax\ge 1$) compared to when it is a set partitioning problem (...
Rom's user avatar
  • 41
0 votes
2 answers
91 views

"GLPK: No Primal Feasible Solution" for Travelling Salesman Problem (Dantzig–Fulkerson–Johnson formulation)

I have a problem with implementing the Dantzig–Fulkerson–Johnson formulation to solve the following Travelling Salesman Problem: \begin{bmatrix} M & 21 & 17 & 19 & 21 & 22\\ 26 &...
satk0's user avatar
  • 123
2 votes
0 answers
95 views

Understanding the condition of the bounded variable algorithm in the linear programming

Following is the section 7.3 of Operation Research An Introduction by Hamdy A. Taha, Define the upper-bounded LP model as, $$\max z=\{CX|(A,I)X=b,0\leq X\leq U\}$$ The bounded algorithm uses only the ...
N00BMaster's user avatar
1 vote
1 answer
160 views

Primal-Dual Simplex Algorithm

Are there any recommended textbooks or notes to learn the details about the primal-dual simplex algorithm?
Lin Sen's user avatar
  • 25
0 votes
0 answers
69 views

Constants in Penalty Function in Linear Optimization

A constant in a linear optimization problem does not influence the decision variables and thus may be discarded (as in this example: max z = x_1 + 2x_2 + 3x_3 + 37)....
Lukas's user avatar
  • 101
1 vote
0 answers
137 views

Non-Linear objective function due to piecewise component (part 2)

This is a follow up to this question: Non-Linear objective function due to piecewise component Consider a piecewise function but now with three segments but the objective remains the same as: $\sum_{n}...
akkha's user avatar
  • 67
2 votes
1 answer
128 views

logic constraints for IP model

I have been struggling with the formulation of logic constraints. Is there any source you would recommend to understand the topic better or trick of formulation of the constraints?
uni_lad's user avatar
  • 39
1 vote
2 answers
358 views

PuLp is ignoring all of the constraints given to it

I am trying to solve a portfolio optimization problem using PuLP where given a dictionary of stock tickers and their returns for the day, returns a set of weights for each stock such that portfolio ...
Josh Smith's user avatar
1 vote
0 answers
263 views

Deriving a valid inequality

Given a set of facilities $I$ and days $J$, each facility $i \in I$ has a capacity of $C_i$, and a set of days $J$ where in each day $j \in J$ there's a total demand of $q_j$ that can be satisfied by ...
CHE's user avatar
  • 113
1 vote
1 answer
94 views

How to understand the basis of LP problems given by HiGHS solver?

Here is part of a ".bas" file given by HiGHS using serial dual simplex method to solve an LP problem: HiGHS v1 Valid # Columns 57471 3 1 1 3 3 1 1 3 3 1 1 3 1 3 3 1 ... What does the number &...
andy's user avatar
  • 77
2 votes
0 answers
97 views

log-log regression as reward function in optimization problem

Consider the model $\hat{y}_t = e^{\text{trend} + \text{seasonality}} \prod_k^K x_{k, t}^{b_k}$ where $K$ denotes different investment alternatives. You can think that trend and seasonality are ...
pete lewis's user avatar
0 votes
1 answer
96 views

Implementing linear programming algorithms

I am learning linear programming through the book Introduction to Linear Optimization by Dimitris Bertsimas. Many of the exercises can be implemented in code. This is an example of such an exercise: (...
Emanuel's user avatar
0 votes
0 answers
48 views

Distributed coloring of nodes of sensor ntwork

I have the same graph coloring problem as in Coloring of nodes of a sensor network @RobPratt and @prubin have proposed some very good solutions. This time I am or interested in distributed coloring ...
KGM's user avatar
  • 2,285
1 vote
0 answers
87 views

Optimize cherry picking runs

I am trying to optimize a cherry picking procedure on 96-well microplates. The plates are 12X8 (12 columns, 8 rows). We pass a command file that has many lines like this to a robot: ...
Ryan's user avatar
  • 111
3 votes
1 answer
232 views

Formulation of binary constraint with the least binary variables for linear programming

I am currently working on a formulation for a linear program of a complex problem. At the moment I am facing to formulate the following logical condition: There are two binary variables. Let's name ...
Nicolas Kaiser's user avatar
1 vote
1 answer
72 views

how do I find the dual when a variable has an upper bound?

What is the dual of this primal LP? $$ max~c^Tx $$ $$ s.t.~Ax=0 $$ $$ 0 \leq x \leq d,~d \in \mathbb{R}_+^n $$
Brannon's user avatar
  • 900
2 votes
1 answer
85 views

Optimization Problem with a Penalty Factor

I am working on an investment optimization problem where I'm trying to maximize returns over a 20-year period with a given total budget. The investment involves an initial capital and annual ...
Francesco's user avatar
2 votes
1 answer
132 views

How to select intermediate nodes in a network?

I have a network where nodes are connected as shown in the Figure . Nodes 2 and 4 have a connection to the cloud node. I am writing constraints where at least one node with a connection to the cloud ...
bsha's user avatar
  • 81
1 vote
2 answers
206 views

Linearizing if else conditions in ILP

We are given three binary indicator variables $X_{ij}, Y_{jk}$ and $Z_{jl}$. Write linear constraints such that, a) if $X_{ij}$ is equal to 1, then for that $j$ when $X_{ij} = 1$, exactly one $Y_{jk} =...
ephemeral's user avatar
  • 897
0 votes
1 answer
91 views

For an ILP relaxed to LP is the LP solution objective always less than the ILP solution?

If an Integer Linear Programming (ILP) problem is relaxed to a Linear Programming (LP) problem, is the objective value of the LP always less than the same ILP problem? Why?
ephemeral's user avatar
  • 897
4 votes
2 answers
1k views

Which solvers should I use to solve large, but extremely sparse LP problems with 100-500 thousand variables?

I would like to solve the following type of LP problems: where M and N are very large numbers, they are on the order of a few hundreds of thousands and tens of thousands, respectively. As is clear ...
TobiR's user avatar
  • 143
2 votes
0 answers
72 views

Approximating an LP with an exponential number of variables and an almost-separation-oracle to its dual

Problem settings: we have $n$ agents and a set $\mathcal{S}$ of possible world-states, where the size of $\mathcal{S}$ is exponential with respect to $n$. Each agent $j$ has a utility function $u_j\...
eden hartman's user avatar
2 votes
2 answers
525 views

How to handle strict inequalities?

Perhaps two trivial questions: What kind of problem is the following (please note the strict inequality)? How do we solve it? $$\min_{x\geq 0}\{c^\top x: Ax < b\}$$
k88074's user avatar
  • 1,661
0 votes
0 answers
17 views

Problem in understanding an equation from a paper about iterative Linear-Quadratic Regulator

I'm reading a paper about iterative Linear-Quadratic Regulator (iLQR) and there are a lot of points that I don't understand. https://homes.cs.washington.edu/~todorov/papers/TassaICRA14.pdf I think ...
user900476's user avatar
0 votes
0 answers
94 views

Transforming a quadratic constraint into a linear constraint

I have a problem with a quadratic constraint and I want to transform it into a linear constraint. This would help to reduce the computational time of my problem. Following constraint should be ...
Adri's user avatar
  • 11
0 votes
2 answers
84 views

Formulating assignment problem with people attributes that need to be balanced per assignment attribute in or-tools, CP-sat

I'm trying to do an assignment problem with the following characteristics: I have two sets that need to be matched with each other, set A (Students) and set B (Class combinations). Set A and B have ...
Riezz's user avatar
  • 41
3 votes
1 answer
457 views

How to reduce an LP problem already in its standard form?

Suppose we have a feasible LP problem in its standard form. From Ax=b we can directly determine some of its variables and thus we can reduce the problem. For example, from two constraints: x+y+z=2 and ...
andy's user avatar
  • 77
0 votes
2 answers
200 views

How to reduce this problem to linear programming one?

$C$ is a given binary matrix of $M \times N$, $l$ and $b$ both are vectors of size $N$ and $M$ correspondingly, with non-negative elements. For given $k$ we need to find any matrix $A$ of $M \times N$ ...
Moonwalker's user avatar
3 votes
0 answers
64 views

Block Simplex Algorithm, i.e., Block Active Set for Linear Programming

What investigation has there been of Block Simplex Algorithms, i.e., block active set for Linear Programming, i.e., block pivoting? This is a follow-up to Why do active set methods or the simplex ...
Mark L. Stone's user avatar
2 votes
1 answer
151 views

Can one strengthen the Lagrangian dual bound in column generation when there are multiple subproblems?

Consider a Linear Programme (LP) \begin{align} \min && \sum_{i \in I} c_i x_i \\ \text{s.t.} && \sum_{i \in I} a_{ij} x_i &\geq b_j & \quad & \forall j \in J \\ && ...
-1 votes
1 answer
71 views

How to linearize the multiplication of variables and transform this into an MILP?

Let $C=10$, $U=50$ $P_c,c=1,\cdots,C$ and $\alpha_{u,c},u=1,\cdots,U,c=1,\cdots,C$ are optimization variables $\alpha_{u,c}$ is binary $\sigma_{u,c}$, $d_{u,c}$ are known parameters $\min \sum_{c=1}^...
KGM's user avatar
  • 2,285

1
2
3 4 5
17