CP-SAT model on C++

630 views
Skip to first unread message

Giulio Graziani

unread,
Jan 22, 2022, 7:21:47 AM1/22/22
to or-tools-discuss
Untitled.png
Hi,

I previously asked on how to solve this problem with the CP-SAT model and a good guy helped me out with the following python suggestions:

// model.AddMultiplicationEquality(t1, [1000 * a1 + 1000 * x1, 1000 * a1 + 1000 * x1])
// model.Add(sum(1000 * bi * ai) <= 1000 * T)
 // make sure to use at least 8 workers for that. (parameters num_search_workers:8)
 // model.Minimize(sum(ti) * 1.0 / 1e6)

I need to implement this on C++, this is what I tried:
Untitled.png
 
I can't seem to find the right tool to insert the costraint, and last, I get MODEL_INVALID when I run it.

Anyone can help me get this model running?
====================================================================
WARNING: Logging before InitGoogleLogging() is written to STDERR
I0122 13:02:21.483950 11948 OptimaSolver.cpp:96] CpSolverResponse summary:
status: MODEL_INVALID
objective: 0
best_bound: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 0.0013731
usertime: 0.0013732
deterministic_time: 0
gap_integral: 0
====================================================================

Laurent Perron

unread,
Jan 22, 2022, 8:13:09 AM1/22/22
to or-tools-discuss
You need to use DoubleLinearExpr for the objective. 

--The good guy :-)

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/d879e15d-dffe-4ad2-a679-d36357f4b0edn%40googlegroups.com.

Giulio Graziani

unread,
Jan 22, 2022, 8:57:10 AM1/22/22
to or-tools-discuss
Changing :
>> cpModel.Minimize(op::sat::LinearExpr::Sum({ xx1, xx2 }) * (1.0 / 1e6));
to:
 >> cpModel.Minimize(op::sat::DoubleLinearExpr::Sum({ xx1, xx2 }) * (1.0 / 1e6));
still output the same error as before

Giulio Graziani

unread,
Jan 22, 2022, 9:29:20 AM1/22/22
to or-tools-discuss
Update:

I fixed all errors reported in validateCpModel and now I get:


===================================================================
WARNING: Logging before InitGoogleLogging() is written to STDERR
I0122 15:27:14.319508 16372 OptimaSolver.cpp:92] CpSolverResponse summary:
status: INFEASIBLE
objective: NA
best_bound: NA

booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 0.0066761
usertime: 0.0066764
deterministic_time: 0
gap_integral: 0
===================================================================

Since the problem has solutions,  is there a way to get more details on why I get this?

Laurent Perron

unread,
Jan 22, 2022, 9:32:15 AM1/22/22
to or-tools-discuss
can you post the code to somewhere it can be copy pasted ?


To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/cc976302-27ae-4df5-8c20-991e3329ed62n%40googlegroups.com.


--
--Laurent

Giulio Graziani

unread,
Jan 22, 2022, 12:15:18 PM1/22/22
to or-tools-discuss
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model_checker.h"

#include <iostream>

#define MAX_STOCKS_PER_ISIN  99999 // TODO: check what's the limit of Domain constructor

namespace op = operations_research;

// CP-SAT model
op::sat::CpModelBuilder cpModel;
 
// 'A' Constants     
double A1 = 73.5; // (totalAmountToInvest_ * targetWeights_[0] / 100) / stockPrice_[0];     
double A2 = 92.5; // (totalAmountToInvest_ * targetWeights_[1] / 100) / stockPrice_[1];
      
// 'B' Constants       
double B1 =1129.43; //  stockPrice_[0];      
double B2 = 12.49; // stockPrice_[1];
      
// T      
double T = 13300.01; //  totalAmountToInvest_ * 1000;
       
// Variables (0 =< x < inf)       
const op::Domain xDomain(0, MAX_STOCKS_PER_ISIN);
      
const op::sat::IntVar x1 = cpModel.NewIntVar(xDomain).WithName("x1");      
const op::sat::IntVar x2 = cpModel.NewIntVar(xDomain).WithName("x2");
       
const op::sat::IntVar xx1 = cpModel.NewIntVar(xDomain).WithName("xx1");       
const op::sat::IntVar xx2 = cpModel.NewIntVar(xDomain).WithName("xx2");
      
// model.AddMultiplicationEquality(t1, [1000 * a1 + 1000 * x1, 1000 * a1 + 1000 * x1]).       
cpModel.AddMultiplicationEquality(xx1, { 1000 * A1 + 1000 * x1, 1000 * A1 + 1000 * x1 });       
cpModel.AddMultiplicationEquality(xx2, { 1000 * A2 + 1000 * x2, 1000 * A2 + 1000 * x2 });       
      
// model.Add(sum(1000 * bi * ai) <= 1000 * T)  <-- TODO: figure out cpp syntax for this costraint
//cpModel.AddLessOrEqual(op::sat::LinearExpr::Sum({ xx1, xx2 }), { uint64_t(T) });

      
// make sure to use at least 8 workers for that. (parameters num_search_workers : 8)      
op::sat::Model model;      
op::sat::SatParameters pams;      
pams.set_num_search_workers(8);      
pams.set_max_time_in_seconds(10.0);      
model.Add(op::sat::NewSatParameters(pams));
       
// Minimize objective function       
cpModel.Minimize(op::sat::DoubleLinearExpr::Sum({ xx1, xx2 }) * (1.0 / 1e6));
      
auto modelProto = cpModel.Build();      
std::cout << op::sat::ValidateCpModel(modelProto) << std::endl;
       
const op::sat::CpSolverResponse response = SolveCpModel(modelProto, &model);       
LOG(INFO) << CpSolverResponseStats(response);
       
if (response.status() == op::sat::CpSolverStatus::OPTIMAL)       
{               
     std::cout << "x1 = " << SolutionIntegerValue(response, x1) << std::endl;              
     std::cout << "x2 = " << SolutionIntegerValue(response, x2) << std::endl;      

Laurent Perron

unread,
Jan 22, 2022, 2:31:45 PM1/22/22
to or-tools-discuss
after many C++ fixes

#include <iostream>

#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model_checker.h"

#define MAX_STOCKS_PER_ISIN \
  999999999999  // TODO: check what's the limit of Domain constructor

namespace op = operations_research;

int main() {

  // CP-SAT model
  op::sat::CpModelBuilder cpModel;

  // 'A' Constants
  double A1 = 73.5;  // (totalAmountToInvest_ * targetWeights_[0] / 100) /
                     // stockPrice_[0];

  double A2 = 92.5;  // (totalAmountToInvest_ * targetWeights_[1] / 100) /
                     // stockPrice_[1];
  int64_t iA1 = static_cast<int64_t>(A1 * 1000);
  int64_t iA2 = static_cast<int64_t>(A2 * 1000);

  // 'B' Constants
  double B1 = 1129.43;  //  stockPrice_[0];

  double B2 = 12.49;    // stockPrice_[1];
  const int64_t iB1 = static_cast<int64_t>(B1 * 1000);
  const int64_t iB2 = static_cast<int64_t>(B2 * 1000);


  // T
  double T = 13300.01;  //  totalAmountToInvest_ * 1000;
  const int64_t iT = static_cast<int64_t>(T * 1000);


  // Variables (0 =< x < inf)
  const op::Domain xDomain(0, MAX_STOCKS_PER_ISIN);

  const op::sat::IntVar x1 = cpModel.NewIntVar(xDomain).WithName("x1");
  const op::sat::IntVar x2 = cpModel.NewIntVar(xDomain).WithName("x2");

  const op::sat::IntVar xx1 = cpModel.NewIntVar(xDomain).WithName("xx1");
  const op::sat::IntVar xx2 = cpModel.NewIntVar(xDomain).WithName("xx2");

  // model.AddMultiplicationEquality(t1, [1000 * a1 + 1000 * x1, 1000 * a1 +
  // 1000 * x1]).
  cpModel.AddMultiplicationEquality(
      xx1, {iA1 + 1000 * x1, iA1 + 1000 * x1});
  cpModel.AddMultiplicationEquality(
      xx2, {iA2 + 1000 * x2, iA2 + 1000 * x2});

  cpModel.AddLessOrEqual(x1 * iB1 + x2 * iB2, iT);


  // Minimize objective function
  cpModel.Minimize(op::sat::DoubleLinearExpr::Sum({xx1, xx2}) * (1.0 / 1e6));

  // make sure to use at least 8 workers for that. (parameters
  // num_search_workers : 8)

  op::sat::SatParameters pams;
  pams.set_num_search_workers(8);
  pams.set_max_time_in_seconds(10.0);
  pams.set_log_search_progress(true);

  const op::sat::CpSolverResponse response =
      SolveWithParameters(cpModel.Build(), pams);

  LOG(INFO) << CpSolverResponseStats(response);

  if (response.status() == op::sat::CpSolverStatus::OPTIMAL) {
    std::cout << "x1 = " << SolutionIntegerValue(response, x1) << std::endl;
    std::cout << "x2 = " << SolutionIntegerValue(response, x2) << std::endl;
  }
  return 0;
}

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8abf9cb4-a35d-4dd6-93aa-abeac63d99d1n%40googlegroups.com.


--
--Laurent

Giulio Graziani

unread,
Jan 22, 2022, 6:36:39 PM1/22/22
to or-tools-discuss
Thank you very much for your patience!

Thought I keep getting "0" for both x1 and x2 as solutions... seems like something is still off

Laurent Perron

unread,
Jan 23, 2022, 1:42:49 AM1/23/22
to or-tools-discuss
This is the obvious optimal.solution is all ai are >= 0.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/4c2b19d2-50cc-4ac4-bcc3-f97c82a40a7en%40googlegroups.com.

Giulio Graziani

unread,
Jan 23, 2022, 2:58:03 AM1/23/22
to or-tools-discuss

Alright sorry if  keep bothering, but i would love to have this working.

So the [0,0] solution in this case makes sense yes, but the A1 and A2 terms are actually meant to be negative. And when I set them negative:

// 'A' Constants     
double A1 = - 73.5; // (totalAmountToInvest_ * targetWeights_[0] / 100) / stockPrice_[0];     
double A2 = - 92.5; // (totalAmountToInvest_ * targetWeights_[1] / 100) / stockPrice_[1];

I get INVALID_MODEL:
Potential integer overflow in constraint: int_prod { target { vars: 2 coeffs: 1 } exprs { vars: 0 coeffs: 100 offset: -600 } exprs { vars: 0 coeffs: 100 offset: -600 } }

I tried to play around with the domain limts and to reduce the variables size but I still get that

Laurent Perron

unread,
Jan 23, 2022, 5:52:49 AM1/23/22
to or-tools-discuss
So it is time to be a bit more clever with bounds. CP-SAT will reject models that can potentially overflow

#include "absl/flags/flag.h"
#include "absl/flags/parse.h"
#include "absl/flags/usage.h"
#include "ortools/base/commandlineflags.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"

namespace operations_research {
namespace sat {


void SolveSquareAssignment() {
// CP-SAT model
CpModelBuilder cpModel;

const int64_t scaling = 100;

// 'A' Constants
double A1 = -73.5; // (totalAmountToInvest_ * targetWeights_[0] / 100) /
// stockPrice_[0];
double A2 = -92.5; // (totalAmountToInvest_ * targetWeights_[1] / 100) /
// stockPrice_[1];
int64_t iA1 = static_cast<int64_t>(A1 * scaling);
int64_t iA2 = static_cast<int64_t>(A2 * scaling);

// 'B' Constants
double B1 = 1129.43; // stockPrice_[0];
double B2 = 12.49; // stockPrice_[1];
const int64_t iB1 = static_cast<int64_t>(B1 * scaling);
const int64_t iB2 = static_cast<int64_t>(B2 * scaling);

// T
double T = 13300.01; // totalAmountToInvest_ * 1000;
const int64_t iT = static_cast<int64_t>(T * scaling);

// Compute upper bounds for x1 and x2 and create the variables.
const int64_t max_x1 = static_cast<int64_t>(T / B1);
const int64_t max_xx1 = (max_x1 * scaling - iA1) * (max_x1 * scaling - iA1);
const IntVar x1 = cpModel.NewIntVar({0, max_x1}).WithName("x1");
const IntVar xx1 = cpModel.NewIntVar({0, max_xx1}).WithName("xx1");
cpModel.AddMultiplicationEquality(
xx1, {iA1 + scaling * x1, iA1 + scaling * x1});

const int64_t max_x2 = static_cast<int64_t>(T / B2);
const int64_t max_xx2 = (max_x2 * scaling - iA2) * (max_x2 * scaling - iA2);
const IntVar x2 = cpModel.NewIntVar({0, max_x2}).WithName("x2");
const IntVar xx2 = cpModel.NewIntVar({0, max_xx2}).WithName("xx2");
cpModel.AddMultiplicationEquality(
xx2, {iA2 + scaling * x2, iA2 + scaling * x2});

// Capacity constraint.
cpModel.AddLessOrEqual(x1 * iB1 + x2 * iB2, iT);

// Minimize objective function
cpModel.Minimize(DoubleLinearExpr::Sum({xx1, xx2}) * (1.0 / scaling / scaling));

// make sure to use at least 8 workers for that. (parameters
// num_search_workers : 8)
SatParameters parameters;
parameters.set_num_search_workers(8);
parameters.set_max_time_in_seconds(10.0);
parameters.set_log_search_progress(true);
const CpSolverResponse response =
SolveWithParameters(cpModel.Build(), parameters);

if (response.status() == CpSolverStatus::OPTIMAL) {
std::cout << "x1 = " << SolutionIntegerValue(response, x1) << std::endl;
std::cout << "x2 = " << SolutionIntegerValue(response, x2) << std::endl;
}
}

} // namespace sat
} // namespace operations research

int main(int argc, char** argv) {
absl::SetFlag(&FLAGS_logtostderr, true);
google::InitGoogleLogging(argv[0]);
absl::ParseCommandLine(argc, argv);
operations_research::sat::SolveSquareAssignment();
return 0;
}

outputs

Starting CP-SAT solver v9.2.10115

Parameters: max_time_in_seconds: 10 log_search_progress: true num_search_workers: 8


Initial optimization model '':

#Variables: 4 (2 in floating point objective)

  - 1 in [0,11]

  - 1 in [0,1064]

  - 1 in [0,71402500]

  - 1 in [0,13374922500]

#kIntProd: 2

#kLinear2: 1


Starting presolve at 0.00s

[Scaling] Floating point objective has 2 terms with magnitude in [0.0001, 0.0001] average = 0.0001

[Scaling] Objective coefficient relative error: 5.34579e-07

[Scaling] Objective worst-case absolute error: 0.718813

[Scaling] Objective scaling factor: 10000

[ExtractEncodingFromLinear] #potential_supersets=0 #potential_subsets=0 #at_most_one_encodings=0 #exactly_one_encodings=0 #unique_terms=0 #multiple_terms=0 #literals=0 time=4e-06s

[Probing] deterministic_time: 0 (limit: 1) wall_time: 4e-06 (0/0)

[DetectDuplicateConstraints] #duplicates=0 time=2.3e-05s

[DetectDominatedLinearConstraints] #relevant_constraints=1 #work_done=0 #num_inclusions=0 #num_redundant=0 time=3e-06s

[ProcessSetPPC] #relevant_constraints=0 #num_inclusions=0 work=0 time=2.3e-05s

[Probing] deterministic_time: 0 (limit: 1) wall_time: 1e-06 (0/0)

[DetectDuplicateConstraints] #duplicates=0 time=6e-06s

[DetectDominatedLinearConstraints] #relevant_constraints=1 #work_done=0 #num_inclusions=0 #num_redundant=0 time=1e-06s

[ProcessSetPPC] #relevant_constraints=0 #num_inclusions=0 work=0 time=1e-06s


Presolve summary:

  - 3 affine relations were detected.

  - rule 'affine: new relation' was applied 3 times.

  - rule 'int_prod: divide product by constant factor' was applied 2 times.

  - rule 'int_square: reduced target domain.' was applied 2 times.

  - rule 'linear: remapped using affine relations' was applied 1 time.

  - rule 'linear: simplified rhs' was applied 1 time.

  - rule 'presolve: 0 unused variables removed.' was applied 1 time.

  - rule 'presolve: iteration' was applied 2 times.

  - rule 'variables: canonicalize affine domain' was applied 3 times.


Presolved optimization model '':

#Variables: 4 (2 in objective)

  - 1 in [0][63][127][192][258][325][393][462][532][603][675][748]

  - 1 in [0,11]

  - 1 in [0,1064]

  - 1 in [0,3775249]

#kIntProd: 2

#kLinear2: 1


Preloading model.

#Bound   0.00s best:inf   next:[3906.24791,949213.993] initial_domain

#Model   0.00s var:4/4 constraints:3/3


Starting Search at 0.00s with 8 workers and subsolvers: [ default_lp, reduced_costs, pseudo_costs, no_lp, max_lp, core, feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, rins_lns_default, rens_lns_default ]

#1       0.00s best:12462.4933 next:[3906.24791,12462.2433] core fixed_bools:0/2

#2       0.00s best:12278.4934 next:[3906.24791,12278.2434] core fixed_bools:1/3

#3       0.00s best:12096.4935 next:[3906.24791,12096.2435] core fixed_bools:2/4

#4       0.00s best:12044.4936 next:[3906.24791,12044.2436] no_lp fixed_bools:2/12

#5       0.00s best:11882.4936 next:[3906.24791,11882.2436] no_lp fixed_bools:2/13

#6       0.00s best:11722.4937 next:[3906.24791,11722.2437] no_lp fixed_bools:2/14

#7       0.00s best:11564.4938 next:[3906.24791,11564.2438] no_lp fixed_bools:2/15

#8       0.00s best:11408.4939 next:[3906.24791,11408.2439] no_lp fixed_bools:2/16

#9       0.00s best:11254.494 next:[3906.24791,11254.244] no_lp fixed_bools:2/17

#10      0.00s best:11102.4941 next:[3906.24791,11102.2441] no_lp fixed_bools:3/18

#11      0.00s best:10952.4941 next:[3906.24791,10952.2441] no_lp fixed_bools:5/19

#12      0.00s best:10804.4942 next:[3906.24791,10804.2442] no_lp fixed_bools:6/20

#13      0.00s best:10658.4943 next:[3906.24791,10658.2443] no_lp fixed_bools:6/21

#14      0.00s best:10514.4944 next:[3906.24791,10514.2444] no_lp fixed_bools:6/22

#15      0.00s best:10372.4945 next:[3906.24791,10372.2445] no_lp fixed_bools:7/23

#16      0.00s best:10232.4945 next:[3906.24791,10232.2445] no_lp fixed_bools:8/24

#17      0.00s best:10094.4946 next:[3906.24791,10094.2446] no_lp fixed_bools:10/25

#18      0.00s best:9958.49468 next:[3906.24791,9958.24468] no_lp fixed_bools:12/26

#19      0.00s best:9824.49475 next:[3906.24791,9824.24475] no_lp fixed_bools:13/27

#20      0.00s best:9692.49482 next:[3906.24791,9692.24482] no_lp fixed_bools:13/28

#21      0.00s best:9562.49489 next:[3906.24791,9562.24489] no_lp fixed_bools:13/29

#22      0.00s best:9434.49496 next:[3906.24791,9434.24496] no_lp fixed_bools:14/30

#23      0.00s best:9308.49502 next:[3906.24791,9308.24502] no_lp fixed_bools:15/31

#24      0.01s best:9184.49509 next:[3906.24791,9184.24509] pseudo_costs fixed_bools:1/9

#25      0.01s best:9162.4951 next:[3906.24791,9162.2451] core fixed_bools:20/22

#26      0.01s best:9062.49516 next:[3906.24791,9062.24516] no_lp fixed_bools:19/33

#27      0.01s best:9018.49518 next:[3906.24791,9018.24518] core fixed_bools:21/23

#28      0.01s best:8942.49522 next:[3906.24791,8942.24522] no_lp fixed_bools:20/34

#29      0.01s best:8824.49528 next:[3906.24791,8824.24528] no_lp fixed_bools:20/35

#30      0.01s best:8708.49534 next:[3906.24791,8708.24534] no_lp fixed_bools:21/36

#31      0.01s best:8594.49541 next:[3906.24791,8594.24541] no_lp fixed_bools:21/37

#32      0.01s best:8482.49547 next:[3906.24791,8482.24547] no_lp fixed_bools:22/38

#33      0.01s best:8372.49552 next:[3906.24791,8372.24552] no_lp fixed_bools:22/39

#34      0.01s best:8264.49558 next:[3906.24791,8264.24558] no_lp fixed_bools:24/40

#35      0.01s best:8158.49564 next:[3906.24791,8158.24564] no_lp fixed_bools:24/41

#36      0.01s best:8054.49569 next:[3906.24791,8054.24569] no_lp fixed_bools:24/42

#37      0.01s best:7952.49575 next:[3906.24791,7952.24575] no_lp fixed_bools:24/43

#38      0.01s best:7852.4958 next:[3906.24791,7852.2458] no_lp fixed_bools:24/44

#39      0.01s best:7754.49585 next:[3906.24791,7754.24585] no_lp fixed_bools:24/45

#40      0.01s best:7688.49589 next:[3906.24791,7688.24589] core fixed_bools:31/33

#41      0.01s best:7566.49596 next:[3906.24791,7566.24596] core fixed_bools:32/34

#42      0.01s best:7564.49596 next:[3906.24791,7564.24596] no_lp fixed_bools:31/47

#43      0.01s best:7472.49601 next:[3906.24791,7472.24601] no_lp fixed_bools:32/48

#44      0.01s best:7382.49605 next:[3906.24791,7382.24605] no_lp fixed_bools:32/49

#45      0.01s best:7294.4961 next:[3906.24791,7294.2461] no_lp fixed_bools:32/50

#46      0.01s best:7208.49615 next:[3906.24791,7208.24615] no_lp fixed_bools:32/51

#47      0.01s best:7124.49619 next:[3906.24791,7124.24619] no_lp fixed_bools:32/52

#48      0.01s best:7042.49624 next:[3906.24791,7042.24624] default_lp fixed_bools:15/35

#49      0.01s best:6962.49628 next:[3906.24791,6962.24628] no_lp fixed_bools:35/54

#50      0.01s best:6884.49632 next:[3906.24791,6884.24632] no_lp fixed_bools:35/55

#51      0.01s best:6808.49636 next:[3906.24791,6808.24636] no_lp fixed_bools:35/56

#52      0.01s best:6734.4964 next:[3906.24791,6734.2464] max_lp fixed_bools:21/41

#53      0.01s best:6662.49644 next:[3906.24791,6662.24644] core fixed_bools:38/40

#54      0.01s best:6558.49649 next:[3906.24791,6558.24649] core fixed_bools:39/41

#55      0.01s best:6456.49655 next:[3906.24791,6456.24655] core fixed_bools:40/42

#56      0.01s best:6356.4966 next:[3906.24791,6356.2466] core fixed_bools:41/43

#57      0.01s best:6258.49665 next:[3906.24791,6258.24665] core fixed_bools:42/44

#58      0.01s best:6162.49671 next:[3906.24791,6162.24671] core fixed_bools:43/45

#59      0.01s best:6068.49676 next:[3906.24791,6068.24676] core fixed_bools:44/46

#60      0.01s best:5976.49681 next:[3906.24791,5976.24681] core fixed_bools:45/47

#61      0.01s best:5886.49685 next:[3906.24791,5886.24685] core fixed_bools:46/48

#62      0.01s best:5798.4969 next:[3906.24791,5798.2469] core fixed_bools:47/49

#63      0.01s best:5712.49695 next:[3906.24791,5712.24695] core fixed_bools:48/50

#64      0.01s best:5628.49699 next:[3906.24791,5628.24699] core fixed_bools:49/51

#65      0.01s best:5546.49703 next:[3906.24791,5546.24704] core fixed_bools:50/52

#66      0.01s best:5466.49708 next:[3906.24791,5466.24708] core fixed_bools:51/53

#67      0.01s best:5388.49712 next:[3906.24791,5388.24712] core fixed_bools:52/54

#68      0.01s best:5312.49716 next:[3906.24791,5312.24716] core fixed_bools:53/55

#69      0.01s best:5238.4972 next:[3906.24791,5238.2472] core fixed_bools:54/56

#70      0.01s best:5222.49721 next:[3906.24791,5222.24721] max_lp fixed_bools:40/68

#71      0.01s best:5166.49724 next:[3906.24791,5166.24724] core fixed_bools:55/57

#72      0.01s best:5090.49728 next:[3906.24791,5090.24728] no_lp fixed_bools:57/64

#73      0.01s best:4962.49735 next:[3906.24791,4962.24735] no_lp fixed_bools:58/65

#74      0.01s best:4902.49738 next:[3906.24791,4902.24738] no_lp fixed_bools:58/66

#75      0.01s best:4844.49741 next:[3906.24791,4844.24741] no_lp fixed_bools:59/67

#76      0.01s best:4836.49741 next:[3906.24791,4836.24741] core fixed_bools:58/60

#77      0.01s best:4776.49745 next:[3906.24791,4776.24745] core fixed_bools:59/61

#78      0.01s best:4748.49746 next:[3906.24791,4748.24746] pseudo_costs fixed_bools:35/60

#79      0.01s best:4718.49748 next:[3906.24791,4718.24748] core fixed_bools:60/62

#80      0.01s best:4662.49751 next:[3906.24791,4662.24751] core fixed_bools:61/63

#81      0.01s best:4632.49752 next:[3906.24791,4632.24752] no_lp fixed_bools:66/71

#82      0.01s best:4608.49754 next:[3906.24791,4608.24754] reduced_costs fixed_bools:16/18

#83      0.01s best:4584.49755 next:[3906.24791,4584.24755] no_lp fixed_bools:66/72

#84      0.01s best:4538.49757 next:[3906.24791,4538.24757] no_lp fixed_bools:66/73

#85      0.01s best:4494.4976 next:[3906.24791,4494.2476] no_lp fixed_bools:66/74

#86      0.01s best:4452.49762 next:[3906.24791,4452.24762] no_lp fixed_bools:66/75

#87      0.01s best:4412.49764 next:[3906.24791,4412.24764] no_lp fixed_bools:66/76

#88      0.01s best:4374.49766 next:[3906.24791,4374.24766] no_lp fixed_bools:66/77

#Bound   0.01s best:4374.49766 next:[4032.24784,4374.24766] core

#89      0.01s best:4338.49768 next:[4032.24784,4338.24768] no_lp fixed_bools:66/78

#90      0.01s best:4304.4977 next:[4032.24784,4304.2477] no_lp fixed_bools:77/79

#91      0.01s best:4272.49772 next:[4032.24784,4272.24772] no_lp fixed_bools:78/80

#92      0.01s best:4242.49773 next:[4032.24784,4242.24773] no_lp fixed_bools:79/81

#93      0.01s best:4214.49775 next:[4032.24784,4214.24775] no_lp fixed_bools:80/82

#94      0.01s best:4188.49776 next:[4032.24784,4188.24776] no_lp fixed_bools:81/83

#95      0.01s best:4164.49777 next:[4032.24784,4164.24777] no_lp fixed_bools:82/84

#96      0.01s best:4142.49779 next:[4032.24784,4142.24779] no_lp fixed_bools:83/85

#97      0.01s best:4122.4978 next:[4032.24784,4122.2478] no_lp fixed_bools:85/86

#98      0.01s best:4104.49781 next:[4032.24784,4104.24781] no_lp fixed_bools:86/87

#99      0.01s best:4088.49781 next:[4032.24784,4088.24781] no_lp fixed_bools:87/88

#100     0.01s best:4074.49782 next:[4032.24784,4074.24782] no_lp fixed_bools:88/89

#101     0.01s best:4062.49783 next:[4032.24784,4062.24783] no_lp fixed_bools:89/90

#102     0.01s best:4052.49783 next:[4032.24784,4052.24783] no_lp fixed_bools:90/91

#103     0.01s best:4044.49784 next:[4032.24784,4044.24784] no_lp fixed_bools:91/92

#104     0.01s best:4038.49784 next:[4032.24784,4038.24784] no_lp fixed_bools:92/93

#105     0.01s best:4034.49784 next:[4032.24784,4034.24784] no_lp fixed_bools:93/94

#106     0.01s best:4032.49784 next:[4032.24784,4032.24784] no_lp fixed_bools:94/95

#Done    0.01s no_lp

#Done    0.01s default_lp

#Model   0.01s var:1/4 constraints:3/3


Sub-solver search statistics:

  'reduced_costs':

     LP statistics:

       final dimension: 3 rows, 2 columns, 4 entries with magnitude in [5.461731e-01, 1.000000e+00]

       total number of simplex iterations: 4

       num solves: 

         - #OPTIMAL: 75

         - #DUAL_FEASIBLE: 1

       managed constraints: 5

       merged constraints: 2

       num simplifications: 1

       total cuts added: 5 (out of 7 calls)

         - 'MIR_1': 2

         - 'SquareLower': 3


  'pseudo_costs':

     LP statistics:

       final dimension: 3 rows, 2 columns, 4 entries with magnitude in [9.260816e-01, 1.000000e+00]

       total number of simplex iterations: 55

       num solves: 

         - #OPTIMAL: 88

       managed constraints: 4

       merged constraints: 1

       num simplifications: 1

       total cuts added: 4 (out of 5 calls)

         - 'MIR_1': 1

         - 'SquareLower': 3


  'max_lp':

     LP statistics:

       final dimension: 3 rows, 2 columns, 0 entries with magnitude in [0.000000e+00, 0.000000e+00]

       total number of simplex iterations: 46

       num solves: 

         - #OPTIMAL: 69

       managed constraints: 4

       merged constraints: 1

       shortened constraints: 4

       num simplifications: 4

       total cuts added: 4 (out of 5 calls)

         - 'MIR_1': 1

         - 'SquareLower': 3



Solutions found per subsolver:

  'core': 29

  'default_lp': 1

  'max_lp': 2

  'no_lp': 71

  'pseudo_costs': 2

  'reduced_costs': 1


Objective bounds found per subsolver:

  'core': 1

  'initial_domain': 1

[Scaling] scaled_objective_bound: 4032.5 corrected_bound: 4032.5 delta: -0.00215569


CpSolverResponse summary:

status: OPTIMAL

objective: 4032.5

best_bound: 4032.5

booleans: 71

conflicts: 65

branches: 91

propagations: 244

integer_propagations: 468

restarts: 13

lp_iterations: 46

walltime: 0.012603

usertime: 0.012603

deterministic_time: 0.000347314

gap_integral: 0.00171635

x1 = 10

x2 = 92

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00



To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f3413b5f-172c-48ee-a976-55737b905d03n%40googlegroups.com.

Izmael Bki

unread,
Feb 18, 2022, 3:36:42 AM2/18/22
to or-tools-discuss

Good afternoon gentlemen,

Pardon for waking up this old thread, but I looked up this group for hours and this have an almost identical optimization problem to mine. In my case, rather than squaring the sum of (Xi - A) in the objective function, I need instead to square the sum of (Xi * Pi - Ai).

So, to refer to the author's existing example (please forgive me if you will), I modified the following lines (for each x):


         const int64_t max_xx1 = (max_x2 * scaling - iA2) * (max_x2 * scaling - iA2);
to:
        const int64_t max_xx1 = (P1 * max_x2 * scaling - iA2) * (max_x2 * scaling - iA2);



         cpModel.AddMultiplicationEquality(
              xx1, {iA1 + scaling * x1, iA1 + scaling * x1});

to:
         cpModel.AddMultiplicationEquality(
              xx1, {iA1 + scaling * x1 * P1 , iA1 + scaling * x1 * P1 });


Where Pi is a decimal number.


Doing so results in a series of (unexpected) zeros as (optimial) solution. What am I doing wrong?

Thank you all for your attention.
I.B.
Op zondag 23 januari 2022 om 11:52:49 UTC+1 schreef Laurent Perron:

Laurent Perron

unread,
Feb 18, 2022, 4:29:39 AM2/18/22
to or-tools-discuss
  const int64_t max_xx1 = (P1 * max_x2 * scaling - iA2) * (max_x2 * scaling - iA2);

missing P1 in the second term

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00


To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f3feded4-1df5-4033-82c9-7082fa0cab88n%40googlegroups.com.

Giulio Graziani

unread,
Feb 18, 2022, 10:29:03 AM2/18/22
to or-tools-discuss
There will be left no single or-tools user behind under Perron's watch!
Reply all
Reply to author
Forward
0 new messages